Monotonic Stack
01 / The one-sentence essence
Maintain a stack whose values stay monotonic — every time the next element would break the order, the elements you pop are exactly the ones for which the current element is the answer.
Problemnext greater element — per indexInput[2, 1, 2, 4, 3, 1]
input
20
11
22
43
34
15
stack →
— empty —
result
?0
?1
?2
?3
?4
?5
Scan left to right. Keep a stack of indices whose values stay strictly decreasing from bottom to top.
step
0 / 16
i
—
stack size
0
result filled
0 / 6
0 / 16
02 / The pattern signature
# next greater element — strictly-decreasing stackstack ← [ ]for i in 0..n−1:while stack not empty and arr[stack.top] < arr[i]:j ← stack.pop()result[j] ← arr[i] // i is j's next greaterstack.push(i)# anything left in stack has no greater on its right → result ← −1
03 / When to recognize this pattern
"next greater / smaller"
For each element, you need the nearest larger (or smaller) element to its right or left. The pattern emits the answer for an index the moment a violator shows up.
"for each, find..."
The answer is per-index, not aggregate — and the relation is positional, not value-based.
"histogram / span"
Largest-rectangle, water-trapping, stock-span — problems where you need bounds defined by the nearest larger / smaller neighbor.
"O(n)"
The expected complexity rules out a naive O(N²) per-index scan and hints at amortized single-pass.
04 / Common pitfalls
i.
Storing values instead of indices.
You almost always need to write to
result[j] when you pop — so the stack has to remember where each popped value came from. Store indices; look up values via arr[stack.top].ii.
< vs ≤ on the inner while.Strict (
<) is "next strictly greater" — duplicates wait on the stack until something larger arrives. Non-strict (≤) is "next greater-or-equal" — equals get popped too and record each other as the answer. They're different problems; the choice silently changes the result on ties.iii.
Forgetting the leftovers at the end.
Indices still on the stack at the end have no next-greater element. Initialize their result to
-1 (or skip them, depending on the spec). It's the easiest part to miss.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. The first two are warm-up next-greater; the last two are where monotonic stack becomes load-bearing.