Maximum Water Trapped by a Pair of Vertical Lines

Leetcode #11

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.

Example:

Note

Idea:

比较简单，如果height left < right, left++, else right--, 再求面积，更新。

Time: O(n)

Code:

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