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.

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]

Sliding Window Maximum

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
}

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