templates · Monotonic stack & deque

Monotonic stack

  • "Next greater" or "next smaller" element, or "how many days until …"
  • For each bar, how far it can stretch left and right (histogram, rectangles)
  • A brute force that scans forward from every index: O(n²) that should be O(n)

Monotonic stack

the one rule

The invariant

The stack holds the indices still waiting for an answer, and their values are in order (decreasing for "next greater").

write it from memory

The template

next greater element

javajava.util.*
/** For each day, how many days until a warmer one (0 if never). The stack holds indices still waiting. */static int[] daysUntilWarmer(int[] temps) {    int[] answer = new int[temps.length];             // default = "never"    Deque<Integer> stack = new ArrayDeque<>();        // indices; bottom → top, their values never go up    for (int i = 0; i < temps.length; i++) {        while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) { // i is the next greater for them            int j = stack.pop();            answer[j] = i - j;                        // resolve j now        }        stack.push(i);                                // i waits for its own greater    }    return answer;}

Store indices, not values: you need the index for distances, and you can always read the value from it.

fill in the blanks — only these lines change per problem

  1. line 3The answer for indices that never get resolved: 0, -1 or n.
  2. line 6The pop rule: < for next greater, > for next smaller. Equal values: decide < or <=.
  3. line 8What a popped index learns: the distance i - j, the value temps[i], or a count.

both borders on pop

javajava.util.*
/** Largest rectangle in a histogram. When a bar is popped, we know both of its borders. */static long largestRectangle(int[] heights) {    Deque<Integer> stack = new ArrayDeque<>();        // indices of bars with increasing heights    long best = 0;    for (int i = 0; i <= heights.length; i++) {        int h = i == heights.length ? 0 : heights[i]; // a 0-height bar at the end flushes the stack        while (!stack.isEmpty() && heights[stack.peek()] >= h) {            int height = heights[stack.pop()];            int left = stack.isEmpty() ? -1 : stack.peek(); // first smaller bar on the left            best = Math.max(best, (long) height * (i - left - 1)); // i is the first smaller on the right        }        stack.push(i);    }    return best;}

When a bar is popped, the bar below it on the stack is its left border and i is its right border.

fill in the blanks — only these lines change per problem

  1. line 6A fake last bar (height 0) so every real bar gets popped and scored.
  2. line 10The score for the popped bar using both borders: height * (i - left - 1).

complexity

What it costs

time O(n)
Every index is pushed once and popped at most once, so the inner while runs at most n times in total.
space O(n)
In the worst case (a decreasing array) every index waits on the stack.

watch out

Common bugs

  • Pushing values instead of indices, then having no way to compute distances or widths.
  • Getting < vs <= wrong in the pop rule. With duplicates, <= treats an equal value as "greater", so a "strictly greater" answer comes out wrong.
  • Forgetting the leftover stack at the end. Add a sentinel, or handle what remains after the loop.

use it

Practise it on

learn it properly