My modified answer from GeeksforGeeks, in JAVA


  • 28
    R

    I was stuck and took an eye on Geeks4Geeks. I got the idea and tried to figure it out by myself...
    It takes me a lot of time to make it through....

    EDITED: Now it is pretty concise....

    public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height==null) return 0;//Should throw exception
        if (height.length==0) return 0;
        
        Stack<Integer> index= new Stack<Integer>();
        index.push(-1);
        int max=0;
        
        for  (int i=0;i<height.length;i++){
                //Start calculate the max value
            while (index.peek()>-1)
                if (height[index.peek()]>height[i]){
                    int top=index.pop();                    
                    max=Math.max(max,height[top]*(i-1-index.peek()));  
                }else break;
                
            index.push(i);
        }
        while(index.peek()!=-1){
        	int top=index.pop();
            max=Math.max(max,height[top]*(height.length-1-index.peek()));
        }        
        return max;
    }
    

    }


  • 5
    K

    A divide and conquer approach whose complexity is strictly O(n log n), though I know there is a liner time algorithm for this.

    int largeArea(int *height, int len) {
    	if (len == 1) return height[0];
    	// Recurse
    	int largeLeft = largeArea(height, len/2);
    	int largeRight = largeArea(height+len/2, len-len/2);
    	// Combine solution
    	int minH = min(height[len/2], height[len/2-1]);
    	int count = 0, largeMid = 0;
    	int leftEnd = len/2-1, rightEnd = len/2;
    	while (leftEnd >= 0 || rightEnd < len) {
    		while (leftEnd >= 0 && height[leftEnd] >= minH)	{
    			leftEnd--;
    			count++;
    		}
    		while (rightEnd < len && height[rightEnd] >= minH) {
    			rightEnd++;
    			count++;
    		}
    		largeMid = max(largeMid, count * minH);
    		if (leftEnd < 0 && rightEnd == len)	break;
    		if (leftEnd >= 0 && rightEnd == len) minH = height[leftEnd];
    		else if (leftEnd < 0 && rightEnd < len)	minH = height[rightEnd];
    		else minH = max(height[leftEnd], height[rightEnd]);
    	}
    	return max(largeMid, max(largeLeft, largeRight));
    }
    

  • 0
    R

    could you give some explaination? thx


  • 0

  • 24
    Z

    The same idea, but it is shorter:

    public class Solution {
        public int largestRectangleArea(int[] height) {
            height = Arrays.copyOf(height, height.length + 1);
    
            int maxRect = 0;
            Stack<Integer> stack = new Stack<Integer>();
            for(int i = 0; i < height.length; ++i) {
                while (!stack.isEmpty() && height[i] < height[stack.peek()]) {
                    int rect = height[stack.pop()] * (stack.isEmpty() ? i : (i-stack.peek()-1));
                    maxRect = Math.max(maxRect, rect);
                }
                stack.push(i);
            }
    
            return maxRect;
        }
    }

  • 0
    O

    One problem with the above solution: If the height keeps increasing, maxRect will never get updated. Here is the revised short version of this solution:

    public int largestRectangleArea(int[] height) {
            int max =0; 
            Stack<Integer> stack = new Stack<Integer>(); 
            for (int i=0; i<=height.length; i++){
                int hi= (i==height.length)? 0:height[i];
                if (stack.isEmpty() || hi > height[stack.peek()]) stack.push(i);
                else {
                    int id = stack.pop(); 
                    int top = height[id]; 
                    max = Math.max(max, top*(stack.isEmpty()?i: i-1-stack.peek())); 
                    i--; 
                }
            }
            return max; 
        }
    

  • 0
    Z

    I think no. Because of the this line:
    height = Arrays.copyOf(height, height.length + 1);
    I copy the original array to the array of bigger size = original+1. The last element is 0 (JVM garantees this). It means when the last element is always lower (or equal in case of zero) than the last element of the original array and becase of this the loop while entered.


  • 0
    Z

    what amazing code,太棒了!


  • 0
    C

    better use empty() method instead of pushing a dummy -1 at the bottom of the stack. It actually reminds me to extend this question to the one that allows negative input.


  • 0
    E

    plus 1 for the ArrayCopy


  • 0
    U

    clever 0 at the end


  • 0
    A

    The array copy idea is simply to brilliant :).


  • 6

    I modified @zerobase solution so that it does not need to copy the array but still keeps its simplicity.

    public class Solution {
        public int largestRectangleArea(int[] heights) {
            
            int maxArea = 0, currArea;
            Deque<Integer> stack = new LinkedList<Integer>();
            
            for ( int i = 0; i <= heights.length; i++ ) {
                while ( !stack.isEmpty() && (i == heights.length || heights[stack.peek()] >= heights[i]) ) {
                    currArea = heights[stack.pop()] * (stack.isEmpty() ? i : (i-stack.peek()-1));
                    maxArea = Math.max(maxArea, currArea);
                }
                stack.push(i); // **
            }
            return maxArea;
        }
    }

  • 0
    Y

    Without padding 0 at the end of original array is ok too.
    The only difference is change the end condition from i<len to i<=len, and change the while() condition.

       for(int i=0; i<=len; i++) {
        	
    		 while(!stack.isEmpty() && (i==len || height[i]<height[stack.peek()])){
        		 int top = stack.pop();
        		 int area = height[top]*(stack.isEmpty()? i: i-stack.peek()-1);
        		 maxArea = Math.max(area, maxArea);
    		 }
        	 stack.push(i);
        	 
         }

  • 0
    This post is deleted!

Log in to reply
 

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