What it is
A monotonic stack is a stack you maintain in sorted order (strictly increasing or strictly decreasing from bottom to top) by popping off any element that violates the order before pushing the new one. Whatever gets popped, at the moment it's popped, has just found the answer it was waiting for — the first larger or smaller value to its right — and whatever's left on the stack at the end is still waiting for one that never came. This turns an apparent O(n²) "compare everyone to everyone ahead of them" problem into a single O(n) pass, because each element is pushed and popped at most once.
When it applies
- You need, for every element, the next (or previous) element that is strictly greater or strictly smaller than it, in a single left-to-right or right-to-left pass.
- The problem is really about spans or widths bounded by a "first taller/shorter thing" on each side (a histogram rectangle, a stretch of days until the weather improves).
- The array is circular, and an element may need to look at elements that wrap around to the beginning — handled by conceptually iterating over the array twice.
- Needing the actual maximum or minimum over a sliding range, rather than "the next element that beats this one," calls for a monotonic deque (fixed window), not this pattern. And elements that can be reordered rather than just deleted while keeping relative order point to a greedy or DP question instead.
Tells in the problem
- "Next greater element," "next warmer day," "next taller building," or the same phrased in reverse ("previous smaller").
- A histogram, skyline, or bar-chart shape where you need the widest or tallest region bounded by shorter neighbors.
- A circular array combined with "wrapping around" language for a next/previous search.
- "Remove k digits/characters to make the result as small/large as possible while keeping relative order" — greedy removal driven by comparing each new character against what's already kept.
- A requirement for O(n) time on a "compare each element against future elements" problem, ruling out the naive nested loop.
The classic mistake
Pushing values onto the stack instead of indices works fine until the problem needs the distance or width between two positions (how many days until the warmer one, how wide a histogram rectangle is) — at that point the value alone can't tell you where it was, and this is the mix-up interviewers report most often. This happens because the comparison logic only ever looks at values, so it's easy to forget that the answer being computed is almost always a function of position, not of the value itself. Guard against it by storing indices on the stack from the start and only dereferencing into the array when you need the actual value to compare.
Questions to start with
- Daily Temperatures — the cleanest one-pass template: a decreasing stack of indices, resolved the moment a warmer day appears.
- Next Greater Element II — the same idea over a circular array, where you iterate past the end to simulate wraparound.
- Car Fleet — a less obvious setup where the monotonic structure comes from arrival times rather than an explicit next-greater question.
- Largest Rectangle in Histogram — the width, not just the existence, of the bounded region is the answer, raising the difficulty a level.
- Remove K Digits — turns the same increasing-stack mechanics into a greedy construction problem instead of a lookup.