LeetCode 84 · Hard · Stack

Largest Rectangle in Histogram

Bars of width 1 stand side by side with the given heights. Return the area of the largest rectangle that fits entirely inside the histogram.

O(n)time
O(n)space
monotonic stacka lower bar ends a rectangle

1–12 integers, 0 to 20

stack{start, height}, rising

public int largestRectangleArea(int[] heights) { int maxArea = 0; Deque<int[]> stack = new ArrayDeque<>(); // {start, height}; top = last for (int i = 0; i < heights.length; i++) { int h = heights[i]; int start = i; while (!stack.isEmpty() && stack.peekLast()[1] > h) { int[] top = stack.pollLast(); int index = top[0], height = top[1]; maxArea = Math.max(maxArea, height * (i - index)); start = index; // h reaches back to here } stack.addLast(new int[] {start, h}); } for (int[] e : stack) { // never cut short: reach the end maxArea = Math.max(maxArea, e[1] * (heights.length - e[0])); } return maxArea;}
i, h
—
start
—
stack
[]
maxArea
0

Why it works

  1. Brute force tries every pair of left and right edges, tracking the lowest bar between them: O(n²). Expanding left and right from every bar is O(n²) too on a flat histogram.
  2. Key insight: the best rectangle is as tall as some bar, and spans as far as that bar can stretch. A bar's rectangle ends at the first lower bar on its right. So keep the bars still stretching on a stack, heights rising from bottom to top. When a lower bar arrives, every taller bar on top has just met its right edge: pop it and measure height × (i - start).
  3. The start trick. The popped bars were all taller than h, so h fits under them too: its rectangle starts where the last popped one started. That left edge is what the dashed span shows on each push.
  4. O(n) time and space. Each bar is pushed once and popped at most once. Pitfall: bars still on the stack at the end never met a lower bar, so they stretch to heights.length; forget that pass and a rising histogram like [1,2,3,4,5] returns 0.
  5. Related: Maximal Rectangle (85) runs this on every row of a 0/1 grid; Trapping Rain Water (42) and Daily Temperatures (739) use the same "wait on a stack until something ends you" pattern.