Description:

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.

解法：

参考：http://blog.csdn.net/a83610312/article/details/8548519

贪心法，证明过程如下：

1.首先假设我们找到能取最大容积的纵线为 i , j (假定i<j)，那么得到的最大容积 C = min( ai , aj ) * ( j- i) ；

2.下面我们看这么些性质：

①: 在 j 的右端没有一条线会比它高！假设存在 k |( j aj) ，那么由 ak> aj，所以 min( ai,aj, ak) =min(ai,aj) ，所以由i, k构成的容器的容积C’ = min(ai,aj ) * ( k-i) > C，与C是最值矛盾，所以得证j的后边不会有比它还高的线；

②:同理，在i的左边也不会有比它高的线；

这说明什么呢？如果我们目前得到的候选：设为 x, y两条线（x< y)，那么能够得到比它更大容积的新的两条边必然在 [x,y]区间内并且 ax’ > =ax , ay’>= ay;

③：所以我们从两头向中间靠拢，同时更新候选值；在收缩区间的时候优先从 x, y中较小的边开始收缩；

直观的解释是：容积即面积，它受长和高的影响，当长度减小时候，高必须增长才有可能提升面积，所以我们从长度最长时开始递减，然后寻找更高的线来更新候补；

代码如下：

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int res = 0;
        while(l<r){
            res = Math.max(res,Math.min(height[l],height[r])*(r-l));
            if(height[l]<height[r]){
                int k = l;
                while(height[k]<=height[l]&&k<r){
                    k++;
                }
                l = k;
            }
            else{
                int k = r;
                while(height[k]<=height[r]&&k>l){
                    k--;
                }
                r = k;
            }
        }
        return res;
    }
}