Monotonic Deque

01 / The one-sentence essence

A deque whose values stay monotonic front → back, with two ends doing distinct jobs: the front evicts when a window slides past; the back drops values dominated by an arriving one. The front always holds the window's max in O(1).
Problemsliding-window max — one value per windowInput[1, 3, -1, -3, 5, 3, 6, 7], k=3
input
10
31
-12
-33
54
35
66
77
deque ↔
— empty —
result
?0
?1
?2
?3
?4
?5
Slide a window of size k = 3 over the array. Keep a deque of indices whose values are strictly decreasing front → back — the front is always the window's max.
step
0 / 39
i
—
deque size
0
windows recorded
0 / 6
0 / 39

02 / The pattern signature

# sliding-window max — strictly-decreasing deque of indicesdq ← [ ] // deque of indicesfor i in 0..n−1:if dq not empty and dq.front ≤ i − k:dq.popFront() // slid out of windowwhile dq not empty and arr[dq.back] < arr[i]:dq.popBack() // dominated; never a future maxdq.pushBack(i)if i ≥ k − 1: result[i − k + 1] ← arr[dq.front]

03 / When to recognize this pattern

"max / min of every window"
Any phrase that says "for every contiguous window of size k, compute the max (or min)" — the classic shape. A naive scan is O(N·k); the monotonic deque collapses it to O(N).
"per-window summary"
The output is one value per window — the same shape as per-index for monotonic stack, but indexed by window position instead.
"shortest subarray such that…"
Many shortest-subarray-with-property problems (LC 862, 1425, 1499) reduce to maintaining a monotonic deque of prefix sums or DP values.
"O(N)" expected
Same hint as monotonic stack — rules out the naive per-window inner loop. If your subroutine already needs O(1) lookup of "max so far in window," you want a monotonic deque.

04 / Common pitfalls

Confusing the two ends.
The deque has two jobs — time (front evicts when sliding past), value (back drops when dominated). They look symmetric but use different conditions: dq.front ≤ i − k on the front; arr[dq.back] < arr[i] on the back. Swapping them silently gives wrong answers.
Storing values instead of indices.
You need to know when the front value entered the window to evict it. Store indices; look up values via arr[dq.front].
< vs ≤ on the back-drop.
Strict (<) keeps duplicates in the deque — fine, but slightly wasteful. Non-strict (≤) drops equals too. For sliding window max either works; for tie-breaking by latest-index, prefer ≤.
Recording before the window is full.
The first k − 1 iterations don't yet have a full window — recording during them yields a wrong-length output. Guard with if i ≥ k − 1.

05 / Go practice — on LeetCode

medium7

01Min Stack— LC 155→02Sum of Subarray Minimums— LC 907→03Grumpy Bookstore Owner— LC 1052→04Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→05Jump Game VI— LC 1696→06Maximum Subarray Min-Product— LC 1856→07Maximum Tastiness of Candy Basket— LC 2517→

hard11

01Largest Rectangle in Histogram— LC 84→02Maximal Rectangle— LC 85→03Sliding Window Maximum— LC 239→04Max Stack— LC 716→05Shortest Subarray with Sum at Least K— LC 862→06Subarrays with K Different Integers— LC 992→07Minimum Number of K Consecutive Bit Flips— LC 995→08Constrained Subsequence Sum— LC 1425→09Max Value of Equation— LC 1499→10Number of Visible People in a Queue— LC 1944→11Maximum Number of Robots Within Budget— LC 2398→