visual walkthrough
Largest Rectangle in Histogram
The defining Hard monotonic-stack problem.
The idea
The best rectangle's height is that of one of the bars, and it stretches as far as the neighbours are at least that tall. A stack of bars in increasing height finds both limits at once.
When a shorter bar arrives, every taller bar on the stack ends here; each pop gives one candidate rectangle.
Complexity
| approach | time | space |
|---|---|---|
| Stretch from every bar | O(n²) | O(1) |
| Monotonic stack | O(n) | O(n) |