Algorithms / Monotonic Stack Next Greater
Least You Need to Know: Monotonic Stacks and Next-Greater Patterns
A monotonic stack keeps elements in sorted stack order so that a new value can resolve many waiting positions at once. This turns repeated scanning into a single left-to-right pass for next-greater and waiting-time style problems.
The least you need to know
- For next-greater problems, the stack usually stores indices whose answer has not been found yet.
- A new larger value can pop smaller waiting values and become their answer.
- The chosen monotone direction depends on whether you need next greater, next smaller, previous greater, or previous smaller.
- Indices are often more useful than raw values because you may need distances or window membership.
- Each index is pushed once and popped once, giving linear-time behavior.
Key notation
stack
LIFO structure holding unresolved candidates
monotone decreasing
stored values decrease from bottom to top
next greater
first later value strictly larger than the current one
Tiny worked example
- Scan array values from left to right.
- Keep a decreasing stack of indices whose next greater value has not appeared yet.
- When a larger value arrives, pop all smaller indices and record the new value or new index as their answer.
- Then push the current index.
Common mistakes
- Students often store values when later they need distances between indices.
- Students often forget that equal values require a deliberate tie rule.
- Students often think monotonic stacks sort the entire array instead of solving pending boundary questions.
How to recognize this kind of problem
- The prompt asks for next greater, warmer day, first taller bar, or nearest later blocker.
- Each position waits for the first later element meeting a comparison.
- A brute-force nested scan would repeatedly revisit the same comparisons.