[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种解法。

暴力解；
取巧解。

暴力解很好理解，将list里任意2数的所有组合，取最大。
时间复杂度： $O(n^2)$ .
取巧解就是双指针的方法。
水槽面积 = $长 \times 宽$

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

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

证明：
假设 $h[L]<h[R]$ , 面积 $S(L, R)$ 左侧向内收缩至 $S(L+1, R)$ 。那么就等于消去了面积 $S(L, R-1)，S(L, R-2), ..., S(L, L+1)$ ，注意这里：

$S(L, R-1)，S(L, R-2), ..., S(L, L+1) < S(L, R)$

因为：

$长$ ：只会小于或等于 $h[L]$ ；
$宽$ ：只会小于 $R-L$ 。

因此，所有消去的面积都 $< S(L, R)$ 。因此消去的状态不会动摇最大面积。

代码：

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

[leetcode] 11. 盛最多的水

推荐阅读更多精彩内容