Concise Java Solution using Stack


  • 0
    B
    public class Solution {
        public int largestRectangleArea(int[] heights) {
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            int maxRec = 0;
            for(int i = 0;i<heights.length;++i){
                while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
                    int height = heights[stack.pop()];
                    maxRec = Math.max(maxRec, height * (i - stack.peek()-1));
                }
                stack.push(i);
            }
            
            int lastIndex = stack.peek();
            while(stack.peek() != -1){
                int height = heights[stack.pop()];
                maxRec = Math.max(maxRec, height * (lastIndex-stack.peek()));
            }
            return maxRec;
        }
    }
    

    Reference:
    http://www.geeksforgeeks.org/largest-rectangle-under-histogram/


Log in to reply
 

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