The idea
A stack only lets you touch its top: push adds an item there, pop removes it, top reads it. Each operation is O(1).
It fits any problem where the most recent unfinished thing must be handled first: matching brackets, evaluating expressions, undoing steps, depth-first search.
A monotonic stack keeps its values in increasing (or decreasing) order by popping everything the new item makes useless. Every item is pushed once and popped at most once, so a whole scan costs O(n). It answers “nearest smaller / greater element” questions.
Sample problem
739. Daily Temperatures ↗ Medium
Given the temperature of each day, return for every day how many days you have to wait for a warmer one, or 0 if none comes.
temperatures = [73,74,75,71,69,72,76,73] output = [1,1,4,2,1,1,0,0]
Why the solution works
Checking every later day for each day is O(n²). Instead, keep the days that are still waiting on a stack.
When a new day arrives, it answers every waiting day that is colder than it. Those days are exactly the ones on top of the stack, because a colder day that arrived after a warmer one sits above it. Pop them, record the wait, then push the new day.
The stack therefore always holds temperatures in falling order: a monotonic stack. Last in, first out is what makes “the most recent colder days” available at the top.
Complexity: O(n) time: each day is pushed and popped at most once. O(n) memory.
Watch out
- Calling
top()orpop()on an empty stack is undefined behaviour: checkempty()first. - Store positions rather than values when the answer needs an index or a distance.
- Choose
>=or>on purpose: it decides how equal values are treated.