10 lines Java Stack


  • 0
    W
    public class Solution {
        public int largestRectangleArea(int[] heights) {
            Stack <Integer> stack = new Stack <> ();
            int maxarea = 0;
            for(int i = 0; i < heights.length; i++) {
                while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                    int last = stack.pop();
                    int top = stack.isEmpty() ? -1 : stack.peek();
                    maxarea = Math.max(maxarea, heights[last] * (i-top-1));
                }
                stack.push(i);
            }
            
            int lastindex = stack.isEmpty() ? 0 : stack.peek();
            while(!stack.isEmpty()) {
                int top = stack.pop();
                int preindex = stack.isEmpty() ? -1 : stack.peek();
                maxarea = Math.max(maxarea, heights[top] * (lastindex - preindex));
            }
            
            return maxarea;
        }
    }

Log in to reply
 

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