leetcode11--Container with most water

# 小郑之家~

### 题目

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.



### 解法

class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
final_max = 0
cur_max = 0

for i in range(len(height)):
for j in range(i+1, len(height)):
temp = min(height[i], height[j])*(j-i)
cur_max = max(cur_max, temp)
final_max = max(final_max, cur_max)
return final_max



class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
water = 0
i = 0
j = len(height)-1
while(i<j):
min_h = min(height[i], height[j])
water = max(min_h*(j-i), water)

# 当没有这个高的时候就pass掉，往前进，停一下的时候已经到了一个更高的地方了
while(height[i]<=min_h and i<j):
i += 1
# 另外一头也做类似的操作
while(height[j]<=min_h and i<j):
j -= 1
return water



class Solution {
public:
int maxArea(vector<int>& height) {
int water =0;
int i=0,j=height.size()-1;
int min_h;
while(i<j){
min_h = min(height[i], height[j]);
water = max(water, min_h*(j-i));

while(i<j && height[i]<=min_h) i++;
while(i<j && height[j]<=min_h) j--;
}
return water;
}
};