O(n) Java solution with explaination


  • 1
    public class Solution {
        public int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length == 0) return 0;
            Stack<Integer> stk = new Stack<>();
            int maxArea = 0, i = 0;
            while (i < heights.length) {
                if (stk.isEmpty() || heights[i] >= heights[stk.peek()]) {
                    stk.push(i);
                    i++;
                } else {
                    int stkTop = stk.pop();
                    int hst = heights[stkTop];
                    int range = stk.isEmpty() ? i : i - stk.peek() - 1;
                    maxArea = Math.max(maxArea, hst * range);
                }
            }
            while (!stk.isEmpty()) {
                int stkTop = stk.pop();
                int hst = heights[stkTop];
                int range = stk.isEmpty() ? i : i - stk.peek() - 1;
                maxArea = Math.max(maxArea, hst * range);
            }
            return maxArea;
        }
    }
    
    • Push things onto the stack when histogram is increasing
    • If we find a histogram bar that is decreasing, pop the stack and multiply by the desired range
    • Once we reach the end, pointer will be at heights.length.
    • Pop and do the same thing as we did in second point
    • All the while keeping track of max area

  • 1
    S

    I vote for the profile pic, lol.


  • 0
    A

    Make C# great again.


Log in to reply
 

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