← Back to the stacks page
Monotonic Stack
A stack kept strictly increasing or decreasing — pushed elements evict everything they dominate. Turns brute-force O(n²) "nearest greater/smaller" scans into O(n).
What to know
- Each element is pushed and popped at most once — that is the amortized O(n) proof.
- Decreasing stack answers "next greater element"; increasing stack answers "next smaller".
- Largest Rectangle in Histogram is the boss fight: widths come from pop-time index gaps.
In the wild: Stock span indicators, skyline problems, compiler expression bounds analysis.
Algorithms to reach for
Next greater element
O(n)For each item, first larger item to the right
Daily temperatures
O(n)Days until a warmer day (indices on the stack)
Largest rectangle in histogram
O(n)Max rectangular area under bars (LeetCode 84)
Trapping rain water (stack variant)
O(n)Water volume between bars
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.