011 container with most water
11. Container With Most Water
题目: https://leetcode.com/problems/container-with-most-water/
难度: Medium
思路：
首先理解花了我一点时间，因为一开始写出来，给了一个例子：
height = [3,2,1,3]
解是 9
| |
| | |
| | | |
1 2 3 4
一开始我的理解走偏的地方是这个9是如何得到的，因为根据最短板原理，明显不可能得到9啊，后来发现是·Find two lines, which together with x-axis forms a container, such that the container contains the most water.
所以代码写起来就简单了,AC无能，超时，时间复杂度O(N^2)
class Solution(object): # 此法超时
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
most_water = 0
for i in range(n-1):
for j in range(i, n):
water = (j-i) * min(height[i], height[j])
most_water = max(water, most_water)
return most_water
题目给的tag是 two pointer，所以上边的策略肯定可以改进，改进的地方就不能是这个一次走一边，而可能是两边都要走。
参考 http://bangbingsyb.blogspot.com/2014/11/leetcode-container-with-most-water.html
思路：
由于ai和aj (i<j) 组成的container的面积：S(i,j) = min(ai, aj) * (j-i)
所以对于任何S(i'>=i, j'<=j) >= S(i,j)，由于j'-i' <= j-i，必然要有min(ai',aj')>=min(ai,aj)才行。同样可以采用头尾双指针向中间移动：
当a(left) < a(right)时，对任何j<right来说
min(a(left),aj) <= a(left) = min(a(left), a(right))j-left < right-left
所以S(left, right) > S(left, j<right)。
这就排除了所有以left为左边界的组合，因此需要右移left。这里证明的非常好。 a[left] < a[right]，需要右移left.
同理，当a(left) > a(right)时，需要左移right。
而当a(left) = a(right)时，需要同时移动left和right。
思路整理： left = 0, right = n-1 1. a[left] < a[right], left++ 2. a[left] > a[right], right-- 3. a[left] = a[right], left++, right-- 终止条件：left >= right
这个证明大快人心
这样写也能过:
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
left, right = 0, n-1
most_water = 0
while left <= right:
water = (right - left) * min(height[left], height[right])
most_water = max(water, most_water)
if height[left] < height[right]:
left += 1
elif height[left] > height[right]:
right -= 1
else:
left += 1
right -= 1
return most_water
