题目描述
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
示例 1:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
官方难度
Medium
解决思路
最简单粗暴的解决思路，两层循环，依次求容量：
- 两层遍历，
j-i为宽，min(nums[i], nums[j])为高，两者相乘 - 互相比较，求最大值。
基于此，我们可以写出的代码如下:
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
max_value = 0
for i in range(len(height)):
for j in range(i+1, len(height)):
current = (j-i)*min(height[i], height[j])
max_value = max(max_value, current)
return max_value
优化
这个题目考查的是双指针问题，设置双指针 i,j 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值 res，直到 i == j 时返回 res。
移动规则： 每次选择短板进行移动，证明如下：
- 设面积为
S(i,j)= min(height[i], height[j])*（j-i）， 每次移动的时候，会变成
j-i-1即宽度会减少。 - 如果移动长板，那么因为面积受制于短板，移动以后高度最多等于之前的短板，但是宽度减小了，因此结果会变小，所以只能移动长板。
根据上面的分析，我们可以很容易的得到直接方案的流程如下：
- 初始化
i, j两个指针为最开始位置和最后的位置。 - 定义max_area 记录最大的面积。
- 计算min(height[i], height[j])*（j-i）和max_area的大小
- 比较
height[i], height[j], 移动较小的值，直到i==j结束。
基于这个流程，我们可以实现类似下面的代码：
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
max_area = 0
i = 0
j = len(height) - 1
while i < j:
area = (j - i) * min(height[i], height[j])
max_area = max(max_area, area)
if height[i] < height[j]:
i += 1
else:
j -= 1
return max_area
总结
这题为Medium难度，感觉有点夸张了，大部分人都能想到暴力破解，关键的优化点是想到移动长板不会使得面积增加，只能移动短板。
