A monotonic stack is a stack you deliberately keep sorted. That is the entire definition, and stated that way it sounds like a curiosity. It becomes indispensable once you notice how many problems are secretly asking the same question: for each element, what is the nearest element to its left or right that beats it?
The question it answers
- →Next greater element to the right.
- →Previous smaller element to the left.
- →How many days until a warmer temperature.
- →How far a histogram bar can extend before it is blocked.
- →Which span a value dominates.
All five are the same query. Brute force is a nested loop, O(n²). A monotonic stack answers all of them in one pass.
The mechanism
Keep a stack of indices whose values are, say, strictly decreasing. When a new element arrives that is larger than the value on top, that top element has just found its next greater element — so pop it and record the answer. Repeat until the invariant holds again, then push the new index.
Every index is pushed exactly once and popped at most once. The inner while looks quadratic and is not — the total number of pops across the whole run is bounded by n.
Choosing the direction
Two decisions, and getting them explicit removes most of the confusion.
- →Increasing or decreasing stack — a decreasing stack finds next greater; an increasing stack finds next smaller.
- →Strict or non-strict comparison — this decides how ties are handled, and it is where duplicate values in histogram problems go wrong.
Largest rectangle in a histogram
This is the payoff problem. For each bar, the largest rectangle with that bar as its limiting height extends left until a shorter bar and right until a shorter bar. Both boundaries are exactly the monotonic-stack query, and a single increasing stack computes them together.
The trailing zero sentinel is worth stealing generally: appending an element guaranteed to beat everything means you never need a separate cleanup pass after the loop.
How to recognise it
If a problem statement contains 'nearest', 'next', or 'previous' together with a comparison — and the brute force is an inner loop scanning outward from each element — check whether a monotonic stack collapses it. It usually does, and the conversion is mechanical once you have chosen the direction and the strictness.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.