【LeetCode two_pointer】11. 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.

题意：给出n个非负值a1, a2, ..., an，(i, ai) 和 (i, 0)组成木桶的一边，找出木桶的两边使木桶

的容积最大

思路：也是一个双指针的题

1.两个指针i,j，当i<j时，不断两头往里面扫描

2.每扫描一个位置计算当前的面积，并刷新最大的面积

3.ai和aj的小者继续往里面递进

时间复杂度O(n)

int maxArea(int* height, int heightSize) {
    if(NULL==height)
        return 0;
    int i=0,j=heightSize-1;
    int area,t_max=0;
    while(i<j){
        area=(j-i)*(height[i]>height[j]?height[j]:height[i]);//计算当前面积
        t_max=(t_max>area?t_max:area);　　　　　　　　　　　　　　//刷新最大面积
        if(height[i]<height[j])　　　　　　　　　　　　　　　　　　//判断需要变化的指针
            i++;
            else
            j--;
    }
    return t_max;
}

Python:

 1 class Solution(object):
 2     def maxArea(self, height):
 3         """
 4         :type height: List[int]
 5         :rtype: int
 6         """
 7         i,j = 0,len(height)-1
 8         vol = 0
 9         while i<j:
10             vol = max(vol,(j-i)*min(height[i],height[j]))
11             if height[i]>height[j]:
12                 j -= 1
13             else:
14                 i += 1
15         return vol
16