# 011 container with most water

### 11. Container With Most Water


height = [3,2,1,3]

|           |
|   |       |
|   |   |   |
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.


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



a(left) < a(right)时，对任何j<right来说

1. min(a(left),aj) <= a(left) = min(a(left), a(right))
2. j-left < right-left

同理，当a(left) > a(right)时，需要左移right

而当a(left) = a(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



apachecn/AiLearning