You are given heights, the heights of the bars in a bar chart, from left to right. Every bar is
1 unit wide, and the bars stand side by side with no gaps.
Return the area of the largest rectangle that fits entirely inside the chart: its bottom on the baseline, its sides on bar edges, and its top no higher than any bar it covers.
Example 1
- Input
- heights = [2, 4, 5, 3, 1, 3]
- Output
- 9
Example 2
- Input
- heights = [6, 2]
- Output
- 6
Constraints
heightsholds 1 to 10⁵ bars.- Every height is between 0 and 10⁴.
Show the pattern
Monotonic stack
The best rectangle as tall as bar i stretches to the nearest lower bar on each side: a "next smaller item" question in both directions, which one stack of rising heights answers.
See monotonic stack in a visualiserShow the approach
The largest rectangle is as tall as the lowest bar it covers, and stretches from just after the nearest lower bar on that bar's left to just before the nearest lower bar on its right. So it is enough to find, for every bar, those two neighbours.
Scan the bars with a stack of indices whose heights rise from bottom to top. Before pushing bar
i, pop every bar at least as tall as it. For a popped bar, i is where its rectangle must stop
on the right, and the bar now on top of the stack is where it must stop on the left (with an
empty stack, it reaches the first bar). Its area is its height times the width between them.
(A bar popped by an equal one may get too narrow a width, but the equal bar later covers the same
rectangle in full.) A final bar of height 0 pops everything. Every bar is pushed and popped once.
Time: O(n) · Space: O(n)