15. Monotonic Stack / Queue

TL;DR

A monotonic stack keeps indices (or values) in strictly increasing or strictly decreasing order so that when a new element violates the order, you pop until the invariant is restored—each pop resolves “who was the previous unresolved barrier?” For next greater element, use a monotonic decreasing stack of indices (values decrease from bottom to top); when a warmer day appears, it resolves pending cooler days. A monotonic deque gives sliding window maximum in amortized O(1) per step.

Core Basics

• Object: stack keeping strict / non-increasing values (or indices) to resolve next greater / nearest smaller in one pass.
• Histogram rule: for each bar, pop while bound breaks; width from previous less index to current.
• Staff-level bar: map to Cartesian tree or range minimum thoughts for deep follow-ups.

Recognition Cues

• Phrases: “next greater,” “next smaller,” “daily temperatures,” “largest rectangle in histogram,” “sliding window maximum.”
• Input: array + queries about boundary elements; or fixed window size k.
• Output: per-index next event, area, or window maxima.

Use-case Lens

• Best when: each element needs the next/previous greater/smaller boundary, or a sliding-window max/min needs a queue.
• Not for: arbitrary range max queries with many offline queries; use segment tree/sparse table.
• Main invariant: the stack/deque keeps candidates in monotonic order, so dominated elements can never be useful later.
• Interview move: describe what a pop proves: the incoming value is the first boundary for popped indices.

Diagram

Step-by-step Visual

Example: Next greater element for [2, 1, 2, 4, 3]. The stack keeps values whose next greater answer is not known yet.

Understanding

Invariant (next greater on the right): the stack holds indices whose next greater element to the right has not been found yet (pending resolution). Scan left to right; while current value breaks decreasing order from the stack top, the current index is the next greater for those popped indices. For next smaller, flip to increasing stack. Deque for window max: store indices whose values are decreasing from front to back; drop from front when outside window, drop from back while new value ≥ back value.

Generic Recipe

Next greater (indices)

1. Initialize empty stack (store indices).
2. For each index from 0 to length-1:
   • While stack not empty and values[index] > values[stackTop], pop stackTop and record answer for stackTop as index.
   • Push index.
3. Remaining stack entries have no greater to the right (use sentinel or -1).

Sliding window max

1. Deque stores indices of candidates, values decreasing from head.
2. Advance window: remove head if index < windowStart.
3. Before push: remove from tail while values[new] >= values[tail].
4. Push new index; record max from deque front at each valid window end.

Complexity

• Time: O(n) for single pass monotonic stack (each index pushed/popped once); sliding window O(n) total.
• Space: O(n) stack/deque storage.

Memory Hooks

• Operational mantra: keep the stack monotone; every pop finalizes the previous candidate against the current value.
• Anti-panic: decide increasing vs decreasing before coding; popping means the current item resolves older candidates.

Study Pattern (SDE3+)

• Recognition drill (10 min): label next-greater, previous-smaller, span, histogram, and sliding-window-max prompts.
• Implementation sprint (25 min): code daily temperatures and histogram rectangle; explain what each pop finalizes.
• Staff follow-up (10 min): discuss equal values, circular arrays, deque expiration, and amortized pop counts.

Generic Code Template

Go

func nextGreaterIndices(values []int) []int {
	length := len(values)
	answer := make([]int, length)
	for index := range answer {
		answer[index] = -1
	}
	stack := make([]int, 0)
	for index := 0; index < length; index++ {
		for len(stack) > 0 && values[index] > values[stack[len(stack)-1]] {
			lastIndex := len(stack) - 1
			topIndex := stack[lastIndex]
			stack = stack[:lastIndex]
			answer[topIndex] = index
		}
		stack = append(stack, index)
	}
	return answer
}

func maxSlidingWindow(values []int, windowSize int) []int {
	if windowSize == 0 {
		return []int{}
	}
	dequeIndices := make([]int, 0)
	result := make([]int, 0, len(values)-windowSize+1)
	for index := 0; index < len(values); index++ {
		if len(dequeIndices) > 0 && dequeIndices[0] <= index-windowSize {
			dequeIndices = dequeIndices[1:]
		}
		for len(dequeIndices) > 0 && values[index] >= values[dequeIndices[len(dequeIndices)-1]] {
			dequeIndices = dequeIndices[:len(dequeIndices)-1]
		}
		dequeIndices = append(dequeIndices, index)
		if index >= windowSize-1 {
			result = append(result, values[dequeIndices[0]])
		}
	}
	return result
}

JavaScript

function nextGreaterIndices(values) {
  const answer = Array(values.length).fill(-1);
  const stack = [];
  for (let index = 0; index < values.length; index++) {
    while (
      stack.length &&
      values[index] > values[stack[stack.length - 1]]
    ) {
      const topIndex = stack.pop();
      answer[topIndex] = index;
    }
    stack.push(index);
  }
  return answer;
}

function maxSlidingWindow(values, windowSize) {
  if (windowSize === 0) return [];
  const dequeIndices = [];
  const result = [];
  for (let index = 0; index < values.length; index++) {
    if (dequeIndices.length && dequeIndices[0] <= index - windowSize) {
      dequeIndices.shift();
    }
    while (
      dequeIndices.length &&
      values[index] >= values[dequeIndices[dequeIndices.length - 1]]
    ) {
      dequeIndices.pop();
    }
    dequeIndices.push(index);
    if (index >= windowSize - 1) {
      result.push(values[dequeIndices[0]]);
    }
  }
  return result;
}

Variants

• Next greater to left: scan right to left with same stack discipline, or reverse logic.
• Largest rectangle in histogram: monotonic increasing stack of bar indices; on pop, width from new boundary to previous smaller.
• Circular array: duplicate indices modulo n for one extra pass, or two-pass trick.

Representative Problems

• 739. Daily Temperatures — next warmer day
• 84. Largest Rectangle in Histogram — increasing stack + width
• 239. Sliding Window Maximum — monotonic deque

Anti-patterns

• Using monotonic stack on unsorted problems that need heap (global top-k, not neighbor boundaries).
• Storing values only when indices are needed to compute widths or distances.
• Sliding window deque forgetting to evict out-of-window indices from the front.
• Confusing next greater vs next greater-or-equal — tie-breaking changes pops.