首页 > itarticle > leetcode: 11. container with most water

leetcode: 11. container with most water

admin 11月 12, 2020 0

11. 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.

对于一对right及left，首先更新最大泳池面积。假设height[left] < height[right],则该泳池面积为height[left] * (right - left),对于left右侧高度小于left的线ｉ，其heigh[i] < height[left], (right - i) < (right - left)其面积一定更小。所以，需要找到left右侧长度大于height[left]的线，作为新的left。对于right同理。

Solution 1 (O(n) 3ms)

public int (int[] height) {
        int left = 0, right = height.length - 1;
    	int maxArea = 0;
    
    	while (left < right) {
    	    maxArea = Math.max(maxArea, 
		(right - left) * (height[left] < height[right] ? 
			height[left] : height[right]));
    		if (height[left] < height[right]) {
    		    int temp = height[left];
    		    while(left < right && height[left] <= temp) left++;
    		}
    		else {
    		    int temp = height[right];
    		    while(left < right && height[right] <= temp) right--;
    		}
    	}
    
    	return maxArea;
}

Solution 2 (O(n) 2ms)

public class Solution {
    public int maxArea(int[] height) {
        int left=0;
        int right = height.length-1;
        int max=0,area;
        while(left<right) {
            int l = height[left];
            int r = height[right]; 
            if( l > r){
                area = (right-left) * r;
                while (height[--right] <= r);
            }else{
                area = (right-left) * l;
                while (height[++left] < l);
            }
            if (area > max) max = area;
        }
        return max;
    }
}