Largest Rectangle in Histogram
Keep a stack of rising bars. Popping a bar bounds its rectangle by the nearest shorter bars on both sides.
Monotonic Stack: Largest rectangle in a histogram
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.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Before this
Taught by the same lesson
Monotonic Stack covers these too, in the same run.