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 / 23
i
—
stack size
0
result filled
0 / 6
0 / 23
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
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].< 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.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
easy4
medium23
01Container With Most Water— LC 11→02Remove Duplicate Letters— LC 316→03Remove K Digits— LC 402→04132 Pattern— LC 456→05Next Greater Element II— LC 503→06Asteroid Collision— LC 735→07Daily Temperatures— LC 739→08Score of Parentheses— LC 856→09Online Stock Span— LC 901→10Sum of Subarray Minimums— LC 907→11Minimum Add to Make Parentheses Valid— LC 921→12Validate Stack Sequences— LC 946→13Check If Word Is Valid After Substitutions— LC 1003→14Next Greater Node In Linked List— LC 1019→15Smallest Subsequence of Distinct Characters— LC 1081→16Reverse Substrings Between Each Pair of Parentheses— LC 1190→17Minimum Remove to Make Valid Parentheses— LC 1249→18Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→19Find the Most Competitive Subsequence— LC 1673→20Jump Game VI— LC 1696→21Maximum Subarray Min-Product— LC 1856→22Sum of Subarray Ranges— LC 2104→23Check if a Parentheses String Can Be Valid— LC 2116→
hard9
01Longest Valid Parentheses— LC 32→02Trapping Rain Water— LC 42→03Largest Rectangle in Histogram— LC 84→04Maximal Rectangle— LC 85→05Sliding Window Maximum— LC 239→06Trapping Rain Water II— LC 407→07Shortest Subarray with Sum at Least K— LC 862→08Maximum Number of Robots Within Budget— LC 2398→09Next Greater Element IV— LC 2454→