Stacks, Queues & Heaps
Monotonic Stack
🍷
Picture this
A fastidious sommelier keeps the rack strictly ascending — any shorter bottle behind a taller one gets pulled.
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
next greaternext smallerwarmer temperaturehistogramspannearest larger
Ask yourself
- “Next/previous greater or smaller element”?
- Largest rectangle / trapping water by bars?
- Maintain a stack that stays increasing or decreasing.
Canonical template
const stack: number[] = [];
for (let i = 0; i < a.length; i++) {
while (stack.length && a[stack[stack.length - 1]] < a[i]) {
const j = stack.pop()!;
ans[j] = i - j;
}
stack.push(i);
}
Common pitfalls
Wrong monotonic direction (inc vs dec).
Storing values when you need indices (or vice-versa).