[leetcode] 11. 盛最多的水

难度：Medium.

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

image.png

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解析：
这里的相关标签是：数组，双指针.

我们也见过一些双指针的题了，包括[leetcode] 19. 删除链表的倒数第N个节点， [leetcode] 3.无重复字符的最长字串，特点都是用两个指针，圈出一片区域，保证这篇区域最大，或者最长，或者不变。

这道题也是这样，是用两个指针，圈出一片区域，保证这篇区域最大。

很自然应对这种找最大的题，会有2种解法。

1. 暴力解；
2. 取巧解。

• 暴力解很好理解，将list里任意2数的所有组合，取最大。
  时间复杂度：.

• 取巧解就是双指针的方法。
  水槽面积 =

最大的长，就左指针L=0，右指针R=n-1。
最大的宽呢，不确定。

指针移动规则：
每次选定围成水槽两板高度 , 中的短板，向中间收窄 1 格。

证明：
假设 , 面积左侧向内收缩至。那么就等于消去了面积，注意这里：

因为：

• ：只会小于或等于；
• ：只会小于。

因此，所有消去的面积都。因此消去的状态不会动摇最大面积。

代码：

def maxArea(height):
    L = 0
    R = len(height)-1
    area_max = min(height[L], height[R])*(R-L)
    
    while L < R:
        if height[L] < height[R]:
            L += 1
        else:
            R -= 1
        
        area_max = max(area_max, min(height[L], height[R])*(R-L))
    
    return area_max