Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

给出的代码模板为:

1
2
3
4
5
6
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""

这道题要求两条竖线组成的区域的面积最大,这就需要两条竖线间的距离尽可能远,且短的那条线要尽可能长(好像有点绕口…),所以面积公式为:

area = min(height[i], height[j]) * (j - i) 其中 i, j 为横坐标,且 i < j.

因为 height 数组中的值是随机的,我们无法控制 min(height[i], height[j]) 部分。但我们可以先让 j - i 最大,然后再根据 height[i]height[j] 的情况相应调整 ij.

所以我们先用两个指针,ij,分别指向数组的头和尾。如果此时height[0] < height[-1],则将 i 向右移。因为此时矩形的宽最大,也就是说此时的矩形说 height[0] 能够形成的最大的矩形,所以也没必要再计算 height[0]heigh[1:-1] 这些竖线组成的面积了,直接将 i 右移。

同样的,如果 height[0] > height[-1],则将 j 左移。

最终可以写成这样代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
i = 0
j = len(height) - 1
max_area = 0
while i < j:
max_area = max(max_area, min(height[i], height[j]) * (j - i))
if height[i] < height[j]:
i += 1
else:
j += 1
return max_area