题目描述

给定 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

解决思路

最简单粗暴的解决思路，两层循环，依次求容量：

1. 两层遍历，j-i为宽，min(nums[i], nums[j])为高，两者相乘
2. 互相比较，求最大值。

基于此，我们可以写出的代码如下:

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。
移动规则： 每次选择短板进行移动，证明如下：

1. 设面积为S(i,j)= min(height[i], height[j])*（j-i）， 每次移动的时候，会变成
   j-i-1即宽度会减少。
2. 如果移动长板，那么因为面积受制于短板，移动以后高度最多等于之前的短板，但是宽度减小了，因此结果会变小，所以只能移动长板。

根据上面的分析，我们可以很容易的得到直接方案的流程如下：

1. 初始化 i, j两个指针为最开始位置和最后的位置。
2. 定义max_area 记录最大的面积。
3. 计算min(height[i], height[j])*（j-i）和max_area的大小
4. 比较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难度，感觉有点夸张了，大部分人都能想到暴力破解，关键的优化点是想到移动长板不会使得面积增加，只能移动短板。