Friday, September 28, 2012

[LeetCode] 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. 

解题思路:
                设2个指针,一个从开头,一个从尾部扫,用最小的高来算出当前的area大小,如果前面的指针的height,比较小,则往后移动到下一个比它大的位置。否则将尾部指针向前移到下一个比当前height大的位置
                     

public int maxArea(int[] height) {
        int start = 0, end = height.length-1;
        int maxArea = 0;
        int h = 0;
        
        while(start < end){
            h = Math.min(height[start], height[end]);
            int area = (end - start) * h;
            
            maxArea = Math.max(maxArea, area);
            
            if(height[start] == h){
              while(start < end && height[start] <= h) start++;
            }else{
              while(start < end && height[end] <= h) end--;
            }
        }
        
        return maxArea;
    }

No comments:

Post a Comment