Monotonic Stack — definition.
Definition
A stack whose elements stay in non-increasing or non-decreasing order.
Complexity
Time O(n) amortized (each element is pushed and popped once).
When to use it
- Next greater / previous smaller element queries.
- Histogram / skyline problems.
- You need to remember the last index where a condition held.
Representative scenarios
- Next Rainy Day — days until next higher temperature.
- Skyline Vault — largest rectangle in a histogram.
- Convoy Merge — stock-span style cumulative count.
Related patterns
Read the full pattern page: Monotonic Stack — template, code, and drills.
Run the free diagnostic.
Ten-minute patterns quiz. No card. Personalized loop starts on the other side.