A solution with O(n*lg(n)) :-O


  • 0
    B

    The solution store a queue, the heigth of the queue is increased, when we visit the ith element, we find the first height in queue that equal to or larger than ith element. we can use binary search for speeding up.
    And we do the same for a revers height array :-O.

    public int maxArea(int[] height){
    	int[] copy = new int[height.length];
    	for(int i = 0; i < height.length; ++i){
    		copy[i] = height[height.length-1-i];
    	}
    	return Math.max(maxArea1(height), maxArea1(copy));
    }
    public int maxArea1(int[] height) {
        int ans = 0;
        int[] que = new int[height.length];
        int tal = -1;
        for(int i = 0; i < height.length; ++i){
            if(tal == -1){
                que[++tal] = i;
            }else{
                int l = 0; int r = tal;
                while(l < r){
                    int m = (l+r)/2;
                    if(height[que[m]] < height[i]){
                        l = m+1;
                    }else{
                        r = m;
                    }
                }
                if(height[que[l]] >= height[i])
                ans = Math.max(ans, (i-que[l])*height[i]);
                if(height[que[tal]] < height[i]) que[++tal] = i;
            }
        }
        return ans;
    }

  • 2
    Y
    Here's my O(n) solution,
    
    public class Solution {
    public int maxArea(int[] height) {
        int l=0;
        int r=0;
        int max =0;
        int temp = 0;
        int n = height.length;
        int h =0;
        
        while(l<=n-1-r){
            if(height[l]>=height[n-1-r]){
                h=height[n-1-r];
            }else{
                h=height[l];
            }
            temp = (n-1-r-l)*h;
            if(temp>max){
                max = temp;
            }
            if(height[l]<=height[n-1-r]){
                l=l+1;
            }else{
                r=r+1;
            }
        }
        return max;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.