What is a Monotonic Stack?
A monotonic stack stores unresolved values in sorted stack order. When a new value breaks that order, it answers questions for one or more earlier values.
You need ordinary stacks, indexes, and comparisons. The short version is: keep only earlier candidates that the current value has not made useless.
The Core Idea: Resolve Waiting Values
In LC 496: Next Greater Element I, the values begin [2,1,2,4,3].
The first 2 waits because no greater value has appeared yet.
When 4 arrives, it is greater than the unresolved 2, so 4 becomes that value's answer.
Why can the popped 2 leave permanently? Its nearest greater value has now been found, and any later value would be farther away.
It is like a stack of people waiting to see someone taller arrive. One tall arrival can answer several shorter people at the top of the stack.
How a New Value Resolves the Stack
The Rule You Keep True
The stack contains only unresolved indexes, and their values follow the chosen monotonic order from bottom to top. Every popped index receives its nearest valid boundary at the current position.
The desired boundary selects the order:
- Next greater keeps a decreasing stack until a larger value arrives.
- Next smaller keeps an increasing stack until a smaller value arrives.
- Daily Temperatures stores indexes so the waiting distance can be calculated.
- Histogram area uses smaller bars as left and right boundaries for a popped height.
Largest Rectangle in Histogram is the one that usually trips us up. After popping a bar, the current index is the right boundary, but the left boundary comes from the new stack top. That width formula is easier to derive from boundaries than to memorize.
Picking the Right Shape
From Rule to Code
- Decide whether unresolved values must stay increasing or decreasing.
- Store indexes when the result uses positions or distances.
- For each value, pop while it resolves the stack top.
- Calculate the popped index's answer from the current position and remaining stack boundary.
- Push the current index and handle unresolved entries after the scan if needed.
Every index is pushed and popped at most once, so the total work is O(n) with O(n) stack space.
When to use it
- •Each value needs the nearest earlier or later value that is greater or smaller.
- •The problem asks how long a value waits before a boundary condition changes.
- •A range remains valid until a smaller or larger value closes it.
- •Repeated scanning from every index would be **O(n²)**.
How to identify it
- •Words such as next greater, next smaller, span, warmer day, or histogram appear.
- •The answer for an earlier item becomes known when a later item arrives.
- •Candidates that are weaker than the current value can never help again.
- •Indexes must be kept so a distance or width can be calculated.
Key insights
- →A monotonic stack keeps unresolved candidates in increasing or decreasing order.
- →The current value resolves stack entries that violate the required order.
- →Each index is pushed once and popped once, which makes the whole scan linear.
- →Store indexes when the answer needs distance, width, or the original position.
- →The remaining stack after the scan represents items with no matching boundary.
Common mistakes
- 01Choosing increasing order when the problem needs a decreasing stack, or the reverse.
- 02Storing values when the result requires index distance.
- 03Popping equal values without deciding how duplicates should behave.
- 04Calculating histogram width from the popped index instead of the new stack boundary.
- 05Running a nested search after popping and losing the linear-time benefit.