Monotonic Stack/Queue
Stack/deque maintained in increasing or decreasing order to answer next-greater/smaller queries.
Next greater element, daily temperatures, largest rectangle in histogram, sliding window max.
Each element is pushed and popped at most once across the whole pass, so total work is linear. The stack can hold up to n elements in a monotonic input.
A monotonic stack maintains elements in strictly increasing or decreasing order from bottom to top. When a new element violates the order, you pop until the order is restored — and each pop typically resolves an answer for the popped element (its 'next greater' or 'next smaller' is the new element). Each element is pushed and popped at most once, so total work is amortized O(n).
The pattern is the standard tool for 'next greater element' style problems: daily temperatures, next greater element I/II, largest rectangle in histogram, trapping rain water. The common thread is 'for each element, find the nearest element on the left/right that satisfies some comparison' — exactly what a monotonic stack solves in one linear pass.
Monotonic deques extend the idea to sliding windows: maintain a deque that holds candidates for the window's max/min, evicting from the back when a larger candidate arrives (they can never be max again) and from the front when the leftmost candidate exits the window. Sliding window maximum is the canonical example, O(n) where the naive approach is O(n*k).
Each element is pushed and popped from a monotonic stack at most once, giving O(n) total work — the inner while loop looks like nested iteration but the amortized cost per element is O(1).
- Storing values instead of indices on the stack, losing the ability to compute distances (e.g. 'days until warmer').
- Using strict vs non-strict comparison incorrectly — 'next strictly greater' uses >, 'next greater or equal' uses >=; getting it wrong breaks problems like 'count of elements with no greater on the right'.
- For largest rectangle in histogram, forgetting to add a sentinel zero at the end to flush remaining stack entries.
- On 'circular array' variants (next greater element II), forgetting to iterate twice (or use index mod n) to handle wraparound.
- For sliding window max with a monotonic deque, evicting based on value comparison without also evicting based on index (window boundary).
- Next greater/smaller element: single pass, stack of indices.
- Daily temperatures: next greater element with distance computed via stored indices.
- Largest rectangle in histogram: stack of increasing heights, sentinel zero to flush.
- Trapping rain water: stack of decreasing heights, compute trapped water on each pop.
- Sliding window maximum: monotonic deque, evict by value and by window boundary.
// import java.util.*;
Deque<Integer> stack = new ArrayDeque<>(); // stores indices
int[] result = new int[n];
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
int j = stack.pop();
result[j] = i - j; // or arr[i], depending on the question
}
stack.push(i);
}
return result;Problems using this pattern
3Easiest first · Blind 75 above NeetCode 150