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.

假设选择的两条线段的横坐标为 i, j. 比较容易想到的方法是计算出所有i, j中的caotainer, 然后选择最大的。类似于数线段个数，时间复杂度O(n^2).

如果我们把i, j指向横轴两端，两者相向运动。

在某一时刻，i前进了m步，j前进了n步。已经记录前一步最大container是cmax，当前contain是csize = (j-i)*min(h[i], h[j]).

cmax = max(cmax, csize), 那么下一步该怎么办呢？

不妨另h[i] <= h[j], 对于任意k > i,

1)如果k >= j, 已经求得最大container是cmax;

2)如果k < j, maxContain = max[(k - i) * min(h[i], h[k])] ,对任意k < j, (k-i) < (j - i)并且min(h[i], h[k]) <= h[i] <= min(h[i], h[j]),

　　因此，maxContain < csize.

由此可得，

 1     int maxArea(vector<int> &height)  2     { 3         int i = 0, j = height.size() - 1; 4         int csize = 0, max = 0; 5          6         while (i < j) 7         { 8             csize = (j - i) * (height[i] > height[j] ? height[j] : height[i]); 9             max = max > csize ? max : csize;10             11             if (height[i] > height[j])12                 j--;13             else14                 i++;15         }16         return max;17     }

leetcode 11.Container With Most Water