5.2 Monotonic Stack & Monotonic Deque

1. What Is a Monotonic Stack / Deque?

The word "monotonic" simply means "always staying in sorted order" (either strictly increasing or strictly decreasing from bottom to top).

A Monotonic Stack is a normal Stack with one extra rule before you push(x):

• Monotonic Decreasing Stack: Before pushing x, pop every item on top of the stack that is smaller than x.
• Monotonic Increasing Stack: Before pushing x, pop every item on top of the stack that is larger than x.

2. Why Do We Need It & How Does It Turn O(N^2) into O(N)?

The Pain Without a Monotonic Stack (O(N^2))

Suppose you are given daily temperatures [73, 74, 75, 71, 69, 72, 76] and asked: "For each day, find the first future day that is warmer (Next Greater Element)." Scanning to the right from every single day takes O(N^2).

The Breakthrough Intuition

Hold indices of "days still waiting for a warmer day" on a Monotonic Decreasing Stack:

• Day 0 (73) waits on the stack: [0 (73)].
• Day 1 (74) arrives! Since 74 > 73, Day 0's wait is over! Pop Day 0, record its answer (1 - 0 = 1 day), and push Day 1.
• Day 3 (71) and Day 4 (69) are cooler than 75, so they pile up on the stack: [2 (75), 3 (71), 4 (69)] (notice they are in decreasing order!).
• When Day 5 (72) arrives, it immediately pops both 69 and 71!

Why is this O(N)? Because even though there is a while loop inside a for loop, each element is pushed onto the stack once and popped at most once across the entire run (2N operations total)!

Cheat Sheet: Which Monotonic Stack Flavor Should You Use?

3. Basic Operations & Walkthroughs (All 4 Languages)

from collections import deque

# 1. Monotonic Decreasing Stack: Next Greater Element / Daily Temperatures -> O(N)
def daily_temperatures(temperatures: list[int]) -> list[int]:
  ans = [0] * len(temperatures)
  stack = []  # stores indices waiting for a warmer day
  for i, temp in enumerate(temperatures):
      while stack and temperatures[stack[-1]] < temp:
          prev_idx = stack.pop()
          ans[prev_idx] = i - prev_idx
      stack.append(i)
  return ans

# 2. Monotonic Decreasing Deque: Sliding Window Maximum -> O(N)
def max_sliding_window(nums: list[int], k: int) -> list[int]:
  dq = deque()  # stores indices in decreasing order of values
  res = []
  for i, x in enumerate(nums):
      while dq and nums[dq[-1]] <= x:
          dq.pop()        # smaller old values can never be window max
      dq.append(i)
      if dq[0] <= i - k:
          dq.popleft()    # evict index that fell out of the left side
      if i >= k - 1:
          res.append(nums[dq[0]])
  return res

4. Core Interview Patterns & Common Traps

# Monotonic Decreasing Stack (Next Greater Element to the Right):
stack = []  # stores indices
for i, x in enumerate(nums):
  while stack and nums[stack[-1]] < x:
      idx = stack.pop()
      next_greater[idx] = x
  stack.append(i)

5. Practice On Your Own (Curated Submodule Problems)