11. 盛最多水的容器

题目：

给定一个长度为?n?的整数数组?height?。有?n?条垂线，第?i?条线的两个端点是?(i, 0)?和?(i, height[i])?。

找出其中的两条线，使得它们与?x?轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。（废话）

【解题思路】

盛水最多的容器是个非常经典的题了，思路也比较简单，想象一下，要使得两端挡板夹住的水能够达到最多，那么决定权必然是在两端挡板中最短的那个，既然如此，那我们就可以从最外围两个挡板开始不断向内找，每次找都记录下两个挡板所夹住的水的最大值，而且，两端挡板向内缩要分三种情况：1. 左端挡板比右端短，此时移动左端向右走一步；2. 右端挡板比左端短，此时移动右端向左走一步；3. 两端挡板一样长，此时两端同时向内走一步；这是因为，最短的挡板才决定能盛多少水，所以我们每次都要移动最短的那一侧。

上述其实是双指针的解题方法，下面上代码：

def maxArea(self, height: List[int]) -> int:
        if len(height) == 2:
            return min(height)
        left, right = 0, len(height)-1
        res = 0
        while left < right:
            s = min(height[left], height[right]) * (right - left)
            res = max(s, res)
            if height[left] > height[right]:
                right -= 1
            elif height[left] < height[right]:
                left += 1
            else:
                left += 1
                right -= 1
        return res