Monotonic Stack and Monotonic Queue

Terminology

Term	Definition
Monotonic stack	A stack that maintains elements in strictly increasing or decreasing order from bottom to top. Elements that violate the order are popped before pushing.
Monotonic queue (deque)	A double-ended queue that maintains elements in monotonic order. Supports efficient insertion and removal from both ends, enabling sliding window min/max in $O(n)$.
Next greater element	For each element in an array, the first element to its right that is strictly larger. A classic monotonic stack problem.

Next smaller element For each element, the first element to its right (or left) that is strictly smaller. Solved with a monotonically decreasing stack. Daily temperatures A LeetCode problem: for each day, find how many days until a warmer temperature. Equivalent to "next greater element" with index distances. Sliding window maximum Finding the maximum element in every contiguous window of size $k$. Solved in $O(n)$ using a monotonic deque. Amortized analysis Each element is pushed and popped at most once across the entire traversal, so total work is $O(n)$ despite the inner while loop. Deque Double-ended queue supporting $O(1)$ push/pop from both front and back. The underlying structure for monotonic queues.

What & Why

Some problems require finding the "next greater" or "next smaller" element for every position in an array. The brute-force approach scans rightward from each element, giving $O(n^2)$ . A monotonic stack solves this in $O(n)$ by maintaining a stack of candidates in sorted order.

The monotonic queue extends this idea to sliding window problems. Instead of recomputing the maximum of each window from scratch in $O(k)$ , a monotonic deque maintains candidates in decreasing order, giving $O(1)$ amortized per window slide.

Both structures share the same core insight: when a new element arrives that is "better" (larger or smaller, depending on the problem), all weaker candidates can be discarded because they will never be the answer for any future query.

How It Works

Monotonic Stack: Next Greater Element

Traverse the array from right to left. Maintain a stack of elements in increasing order (bottom to top). For each element, pop everything smaller (they cannot be the "next greater" for anyone further left), then the stack top is the answer.

Monotonic Deque: Sliding Window Maximum

Maintain a deque of indices in decreasing order of their values. For each new element: remove indices outside the window from the front, remove smaller elements from the back, then push the new index. The front of the deque is always the window maximum.

Complexity Analysis

Problem	Brute Force	Monotonic	Space
Next greater element	$O(n^2)$	$O(n)$	$O(n)$
Daily temperatures	$O(n^2)$	$O(n)$	$O(n)$
Sliding window maximum	$O(nk)$	$O(n)$	$O(k)$
Largest rectangle in histogram	$O(n^2)$	$O(n)$	$O(n)$

Each element is pushed onto the stack (or deque) exactly once and popped at most once. Total operations across all iterations:

$\text{pushes} + \text{pops} \leq 2n = O(n)$

Implementation

Next Greater Element

ALGORITHM NextGreaterElement(A, n)
  INPUT: array A of size n
  OUTPUT: array result where result[i] = next greater element of A[i], or -1

  result = array of size n, filled with -1
  stack = empty stack

  FOR i = n - 1 DOWNTO 0 DO
    WHILE stack is not empty AND stack.top() <= A[i] DO
      stack.pop()
    END WHILE

    IF stack is not empty THEN
      result[i] = stack.top()
    END IF

    stack.push(A[i])
  END FOR

  RETURN result
END

Daily Temperatures

ALGORITHM DailyTemperatures(temps, n)
  INPUT: array temps of size n
  OUTPUT: array result where result[i] = days until warmer temperature

  result = array of size n, filled with 0
  stack = empty stack  // stores indices

  FOR i = n - 1 DOWNTO 0 DO
    WHILE stack is not empty AND temps[stack.top()] <= temps[i] DO
      stack.pop()
    END WHILE

    IF stack is not empty THEN
      result[i] = stack.top() - i
    END IF

    stack.push(i)
  END FOR

  RETURN result
END

Sliding Window Maximum

ALGORITHM SlidingWindowMax(A, n, k)
  INPUT: array A of size n, window size k
  OUTPUT: array of maximum values for each window

  result = empty array
  deque = empty deque  // stores indices

  FOR i = 0 TO n - 1 DO
    // Remove indices outside the window
    WHILE deque is not empty AND deque.front() < i - k + 1 DO
      deque.popFront()
    END WHILE

    // Remove smaller elements from back
    WHILE deque is not empty AND A[deque.back()] <= A[i] DO
      deque.popBack()
    END WHILE

    deque.pushBack(i)

    IF i >= k - 1 THEN
      result.append(A[deque.front()])
    END IF
  END FOR

  RETURN result
END

Real-World Applications

Stock price analysis: "stock span" problems (how many consecutive days was the price lower?) are solved with a monotonic stack in $O(n)$.
Histogram area computation: the largest rectangle in a histogram uses a monotonic stack to find the nearest smaller bar on each side.
Streaming data processing: monotonic deques maintain running min/max over a sliding window in real-time sensor data and financial tick streams.
Task scheduling: finding the next available time slot that meets a constraint uses monotonic structures to avoid rescanning.
Compiler optimization: register allocation and instruction scheduling use stack-based analysis of variable lifetimes.

Key Takeaways

A monotonic stack maintains elements in sorted order by popping weaker candidates before pushing, solving "next greater/smaller" problems in $O(n)$
A monotonic deque extends the idea to sliding windows, maintaining the window max (or min) at the front in $O(1)$ amortized per step
The amortized $O(n)$ guarantee comes from each element being pushed and popped at most once across the entire traversal
Choose increasing stack for "next greater" problems and decreasing stack for "next smaller" problems
When you see "for each element, find the nearest larger/smaller element," reach for a monotonic stack