leetcode11_盛最多水的容器

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

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

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

假如目前指针间距为n, 左侧的线段高度比右侧的高度低，那么我们通过左移右指针来将长度缩短为n-1的做法是没有意义的， 此时如果仍然是左指针对应高度最低则新的形成的面积变成了(n-1) * heightOfLeft ，如果右指针对应的高度更低则更差劲，面积一定比移动前长度为n的面积n * heightOfLeft 小。因为也就是说最大面积一定是当前的面积或者通过移动短的线段得到。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        时间复杂度 O(N)，双指针遍历一次底边宽度 N 
        空间复杂度 O(1)，指针使用常数额外空间
        采用双指针可以避免两次循环，复杂度降低到O（n)
        """
        left, right, area = 0, len(height)-1, 0
        while left < right:
            if height[left] < height[right]:
                area = max(area, height[left]*(right-left))
                left += 1
            else:
                area = max(area, height[right]*(right-left))
                right -= 1
        return area