Pattern 17: Monotonic Stack / Queue

Deep Dive: Monotonic Stack for Next Greater Element

nums = [2, 1, 2, 4, 3]

Process RIGHT to LEFT, maintain decreasing stack:

i=4: val=3, stack=[]        push 3.   stack=[3].    next_greater[4]=-1
i=3: val=4, stack=[3]       3<4, pop. stack=[].     next_greater[3]=-1. push 4. stack=[4]
i=2: val=2, stack=[4]       4>2, ok.  next_greater[2]=4. push 2. stack=[4,2]
i=1: val=1, stack=[4,2]     2>1, ok.  next_greater[1]=2. push 1. stack=[4,2,1]
i=0: val=2, stack=[4,2,1]   1<2, pop. 2<=2, pop. 4>2, ok. next_greater[0]=4. push 2. stack=[4,2]

Result: [4, 2, 4, -1, -1]

Sliding Window Maximum (Monotonic Deque)

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Deque stores INDICES, maintains decreasing values:

i=0: deque=[0]              val=1
i=1: 3>1, pop 0. deque=[1] val=3
i=2: -1<3, append. deque=[1,2]. Window [0..2]: max=nums[1]=3
i=3: -3<-1, append. deque=[1,2,3]. Window [1..3]: max=nums[1]=3
i=4: 5>-3, pop 3. 5>-1, pop 2. 5>3, pop 1. deque=[4]. Window [2..4]: max=5
i=5: 3<5, append. deque=[4,5]. Window [3..5]: max=5
i=6: 6>3, pop 5. 6>5, pop 4. deque=[6]. Window [4..6]: max=6
i=7: 7>6, pop 6. deque=[7]. Window [5..7]: max=7

Maxes: [3, 3, 5, 5, 6, 7]

The deque front is always the window maximum. Remove from back if new element is larger (they will never be the max). Remove from front if index is outside the window.

---

Signal: "Next greater element", "next smaller", "sliding window maximum/minimum", histogram Template: next_greater_element() in templates.py

When to Use

• "Next greater/smaller element" -> monotonic stack
• "Largest rectangle in histogram" -> monotonic increasing stack
• "Sliding window maximum" -> monotonic decreasing deque
• "Daily temperatures" -> monotonic decreasing stack

Two Variants

Monotonic STACK: process array, maintain sorted order on stack
  - Decreasing stack -> finds next GREATER
  - Increasing stack -> finds next SMALLER

Monotonic DEQUE: sliding window max/min
  - Decreasing deque -> front = window maximum
  - Remove from back if new element is larger
  - Remove from front if index outside window

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Daily Temperatures	Phase 1.6	15 min	[ ]
Sliding Window Maximum	Phase 1.6	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Next greater / next smaller element" for each index — the canonical monotonic-stack problem.
• "Largest rectangle in histogram / maximal rectangle in a binary matrix" — area problems where the limiting bar requires next-smaller-on-each-side.
• "Sliding window maximum / minimum" — monotonic deque, front holds the current extreme.
• "Stock span / days until warmer temperature / sum of subarray minimums" — same shape: each element waits for the next break in monotonicity.
• "Remove K digits to get the smallest number / smallest lexicographic subsequence" — a monotonic stack greedily pops elements that violate the desired order.

Anti-signals (looks like this pattern, isn't)

• "Maximum element in a fixed window" when K is small or N is short — a simple loop is clearer; reach for the deque only when N or K is large.
• "Kth largest in a window" — Heap or balanced BST; a monotonic deque tracks only one extreme, not the K-th.
• "Greater element somewhere in the array (not strictly the next)" — sort-based or set-based approach; monotonic stack is specifically for next in index order.