11. Container With Most Water

11. Container With Most Water

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxVal = 0;
        int i = 0, j = height.size() - 1;
        while(i < j)
        {
            maxVal = max(maxVal, (j - i) * min(height[i], height[j]));
            if(height[i] < height[j])
                ++i;
            else
                --j;
        }
        return maxVal;
    }
};

当height[i] < height[j]时，如果不舍弃他而移动右边j，那么结果肯定时小于现在的，所以舍弃i

假设a2,a6为最大，需要证明当left=a2时，右边会移到a6。 即当left=a2,right=a7的下一位时left=a2,left=a6。而这一步必然时height[a2]>height[a7]，若不然，则最小边界为a2，宽度只会减少，则总值减少，所以必定移动a.