CONCEPT · Candidate Master
Monotonic stack
also next greater · next smaller · NGE
A stack kept increasing or decreasing so each index is pushed and popped once. Answers next-greater / next-smaller in linear time.
Intuition
When a new value arrives, everything that was waiting for something better just found it. Pop them, then wait yourself.
When to reach for it
- Next greater / smaller to the left or right
- Largest rectangle in histogram
- CSES Nearest Smaller Values
Usual pits
- Strict vs non-strict compare (`<` vs `<=`)
- Storing values instead of indices when you still need positions
- Forgetting leftovers stay -1
- Circular arrays need a 2n walk