O(n) - AC very easy to understand JAVA solution using stack


  • 0
    N

    Inspired from https://www.youtube.com/watch?v=ZmnqCZp9bBs . Please go through the video for more explanation.

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        int area = 0;
        for (i = 0; i < heights.length; ) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    area = heights[top] * i;
                } else {
                    area = heights[top] * (i - stack.peek() - 1);
                }
                maxArea = Math.max(area, maxArea);
    
            }
    
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            if (stack.isEmpty()) {
                area = heights[top] * i;
            } else {
                area = heights[top] * (i - stack.peek() - 1);
            }
            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    
    }

Log in to reply
 

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