11. 盛最多水的容器

题目：

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

思路：<时间复杂度为O(n)>

设立两个指针，一个从头一个从尾，相向而行遍历数组，每次舍弃较短边

(1) 计算面积最大值的初值，该初值以数组中的第一个元素和最后一个元素构成两边。

(2) 设置首尾两个指针，首指针i指向数组中的第一个元素，尾指针j指向数组中的最后一个元素。

(3) 当首指针i小于尾指针j时，一直循环计算其面积。若计算所得的当前面积大于(1)步骤中所计算得的面积最大值，则更新最大值。每一次循环都舍弃索引i和索引j中较短的那一条边。

为什么每一次循环舍弃索引 i 和索引 j 中较短的那一条边，我们最终得到的结果就会是最大的面积值呢？

反证法：

假设我们现在遍历过程中已经取到目前最优值 height[ i ] 和 height[ j ] ，如果我们想获取容量(面积 w*h)更大，由于长方形的宽是一直减小的，只可能舍弃短的一边而去找更长的一边。

由于整个过程只遍历了一次数组，因此时间复杂度为O(n)，其中n为数组height的长度。而使用空间就是几个变量，故空间复杂度是O(1)。

 1 class Solution:
 2     def maxArea(self, height: List[int]) -> int:
 3         left,right = 0,len(height)-1
 4         res = 0
 5         while left<right:
 6             if height[left]<height[right]:
 7                 h = height[left]
 8                 left += 1
 9             else:
10                 h = height[right]
11                 right -= 1
12             w = right-left+1
13             area = w*h
14             if res < area:
15                 res = area        
16         return res