Monotonic Stack & Queue Pattern

What is a Monotonic Stack?

A monotonic stack maintains elements in strictly increasing or decreasing order. When pushing a new element, pop all elements that violate the monotonic property. This efficiently solves "next greater/smaller" problems in O(n) time instead of O(n²) with brute force.

Two flavors exist: a monotonic increasing stack (bottom to top: smallest to largest) and a monotonic decreasing stack (bottom to top: largest to smallest). The choice depends on whether you are searching for next greater or next smaller elements.

Next Greater Element Pattern

function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1)
  const stack: number[] = [] // indices

  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop()!
      result[idx] = nums[i]
    }
    stack.push(i)
  }
  return result
}
// [2,1,2,4,3] → [4,2,4,-1,-1]

Time complexity: O(n) — each element is pushed and popped at most once. Space complexity: O(n) for the stack.

Sliding Window Maximum (Monotonic Deque)

For sliding window problems, a monotonic deque (double-ended queue) lets you query the window maximum or minimum in O(1) per step.

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = []
  const deque: number[] = []

  for (let i = 0; i < nums.length; i++) {
    while (deque.length > 0 && deque[0] <= i - k) deque.shift()
    while (deque.length > 0 && nums[i] > nums[deque[deque.length - 1]]) deque.pop()
    deque.push(i)
    if (i >= k - 1) result.push(nums[deque[0]])
  }
  return result
}

Largest Rectangle in Histogram

One of the hardest monotonic stack problems. Maintain an increasing stack of bar indices; when a shorter bar is encountered, pop and calculate the area using the popped bar as the height.

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [-1]
  let maxArea = 0
  const h = [...heights, 0] // sentinel to flush stack

  for (let i = 0; i < h.length; i++) {
    while (stack[stack.length - 1] !== -1 && h[i] < h[stack[stack.length - 1]]) {
      const height = h[stack.pop()!]
      const width = i - stack[stack.length - 1] - 1
      maxArea = Math.max(maxArea, height * width)
    }
    stack.push(i)
  }
  return maxArea
}

When to Use Monotonic Stack vs Deque

• Monotonic stack — next greater/smaller element, histogram area, temperature span problems. Elements are processed left-to-right and the answer for each element is determined when a violating element arrives.
• Monotonic deque — sliding window min/max. Need to remove expired elements from the front as the window moves.

Key Pattern Recognition

• Problem asks for "next greater/smaller element" → monotonic stack
• Problem involves a sliding window and asks for min/max → monotonic deque
• Problem involves histograms, buildings, or water trapping → monotonic stack with area calculation
• Brute force is O(n²) due to nested loops over elements → monotonic stack often reduces this to O(n)

Problems to Practice

• Next Greater Element (LC 496) - Classic monotonic stack
• Sliding Window Maximum (LC 239) - Monotonic deque
• Largest Rectangle (LC 84) - Histogram with stack
• Trapping Rain Water (LC 42) - Monotonic stack variation
• Daily Temperatures (LC 739) - Next greater with days count
• Sum of Subarray Minimums (LC 907) - Contribution technique