盛最多水的容器
题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：不能倾斜容器。
示例
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
题解
分析：
设两指针i,j,指向的水槽板高度分别为h[i],h[j],此状态下水槽面积为S(i,j)。由于可容纳水的高度由两板中的短板决定，因此可得如下面积公式：
S(i,j)=min(h[i],h[j])×(j−i)
在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度−1变短：
若向内移动短板，水槽的短板min(h[i],h[j])可能变大，因此下个水槽的面积可能增大。
若向内移动长板，水槽的短板min(h[i],h[j])不变或变小，因此下个水槽的面积一定变小。
因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。
def maxArea(self, height: List[int]) -> int:
# max_area = 0
# for i in range(len(height)):
# for j in range(i+1, len(height)):
# area = (j-i) * min(height[i], height[j])
# if area > max_area:
# max_area = area
# return max_area
# 双指针法
i, j , area = 0, len(height)-1, 0
while i < j:
if height[i] < height[j]:
area = max(area, (j-i) * min(height[i], height[j]))
i += 1
else:
area = max(area, (j-i) * min(height[i], height[j]))
j -= 1
return area算法流程：
初始化：双指针i,j分列水槽左右两端；
循环收窄：直至双指针相遇时跳出；
- 更新面积最大值area；
- 选定两板高度中的短板，向中间收窄一格；
返回值：返回面积最大值area即可；
正确性证明：
若暴力枚举，水槽两板围成面积S(i,j)的状态总数为C(n,2)。
假设状态S(i,j)下h[i]<h[j]，在向内移动短板至S(i+1,j)，则相当于消去了S(i,j−1),S(i,j−2),…,S(i,i+1)状态集合。而所有消去状态的面积一定都小于当前面积（即<S(i,j)），因为这些状态：
短板高度：相比S(i,j)相同或更短（即≤h[i]）；底边宽度：相比S(i,j)更短；因此，每轮向内移动短板，所有消去的状态都不会导致面积最大值丢失，证毕。
复杂度分析：
- 时间复杂度O(N):双指针遍历一次底边宽度N
- 空间复杂度O(1):变量i,j,area使用常数额外空间
悟了
这道题就像相亲一样，越早遇见对的人越好。当我遇到的人都比我自己差的时候，我还是不满足，所以把差的抛弃了，直到遇到一个比自己更好的，那这个人一定就是我所能遇到最好的了。因为自此之后遇到再好的人，ta所超过我的部分对我来说也没有价值，我自己还是那个短板。自此之后遇到同样的人，也没有和ta的时间一样多，而且还可能遇到更差的人。——来自某不知名大佬