Largest Rectangle in Histogram
Keep a stack of rising bars; popping a bar bounds its rectangle by the nearest shorter bars on both sides.
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.
What you will see
Bars as cells; popping a bar draws the rectangle it bounds.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Items announce position from the top or front and value; each step announces the operation and the new top or front.
Reduced motion: Items appear or disappear in place with a crossfade instead of sliding in or out.
Before this
Taught by the same lesson
Monotonic Stack covers these too, in the same run.