AlgoScope

Largest Rectangle in Histogram

Keep a stack of rising bars. Popping a bar bounds its rectangle by the nearest shorter bars on both sides.

Stack and queue algorithms, algorithm, advanced
Pop bar 0 of height 2: area 2.rect 0-0201152632435i2 > 1
Pop bar 0 of height 2: area 2.rect 0-0201152632435i2 > 1

Monotonic Stack: Largest rectangle in a histogram

Decision, step 3 of 14

Bar 1 has height 1, not taller than the top of the stack, 2 at index 0. Pop it: its rectangle reaches right to index 0 and left to index 0 (no shorter bar on the left), width 1, area 2 x 1 = 2. New best.

How monotonic stack works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

Taught by the same lesson

Monotonic Stack covers these too, in the same run.