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.

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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.

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.