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.

思路：

贪心的方法，用left和right分别记录数组的两边，然后哪边小从哪边往里面移动。因为如果另一边的话只可能更小。

简单的证明：

假设一个中间状态时[(i, a), (j, b)]，则 j 右边小于a的边和 i 左边小于b的边都已经遍历过了。若a < b, j 向左移只会更小， j向右移如果是小于a的值则已经遍历，假设有大于a的值（k， c），则a左边一定又有大于c的值（m，d）使得到达j当前的位置（否则按照代码思路，右边指针会停留k在这等待左边指针向右移动到i），也就意味着[（m,d）,（k,c）]访问过或者比它更大的结果访问过，而它一定会大于[(i,a),(k,c)],所以也没有必要再尝试这个状态。综上，j不需要动，i向右移动尝试其他组合。

 1     int min(int a, int b){
 2         if(a<b)
 3             return a;
 4         return b;
 5     }
 6     int maxArea(vector<int> &height) {
 7         // Start typing your C/C++ solution below
 8         // DO NOT write int main() function
 9         int n = height.size();
10         int left = 0, right = n-1;
11         int max = min(height[left], height[right])*(right-left), tmp;
12         while(left < right){
13             if(height[left] < height[right])
14                 left++;
15             else
16                 right--;
17             tmp = min(height[left], height[right])*(right-left);
18             if(tmp > max)
19                 max = tmp;
20         }
21         return max;
22     }