Example
最多装水问题
时间复杂度: O(N)- 空间复杂度: O(1)
image.png
十分经典的一个题，我们来推到一下数学过程：
组成水的面积是，S(i,j) = min(ai, aj) * (j-i)
当height(left) < height(right)时，对于任何left< j < right都存在：
1.min(height[left], height[j]) <= height[left] = min(height[left], height[right])
2.j - left < right - left
根据上列公式推到，对于任何left < j < right来说
S(left, right) = min(height[left], height[right] * (right - left)) 必然大于 S(left, j) = min(height[left], height[j] * (j - left))
这就排除了所有以left为左边界的组合，因此需要右移left
因此得出以下三点结论：
1.height[left] < height[right]， 需要右移left
2.同理，height[left] > height[right]， 需要左移right
3.当height[left] = height[right]， 需要两端同时移动
def maxArea(self, height):
left, right, res = 0, len(height) - 1, 0
while left <= right:
water = min(height[left], height[right]) * (right - left)
res = max(res, water)
if height[left] < height[right]:
left += 1
elif height[left] > height[right]:
right -= 1
else:
left += 1
right -= 1
return res
