Pattern Reference
Monotonic Queue
"Deque maintaining monotonic order for sliding window min/max, range min queries."
Loading...
Deep Dive Tutorial
A monotonic deque answers "what is the maximum in the last k elements?" for every position in O(1) amortized time. The key invariant: the deque holds indices of elements that are candidates to be the current window's answer. Elements that are both older AND smaller than a newly added element can never win — so we evict them from the back. Expired elements (outside window) are evicted from the front.
Monotonic deque template — sliding window maximum
// Sliding window maximum: for every window of size k, find max
// Deque holds indices in DECREASING order of values
function slidingWindowMax(nums, k) {
const deque = []; // indices, front = largest, back = smallest in window
const result = [];
for (let i = 0; i < nums.length; i++) {
// 1. Evict elements outside window from front
while (deque.length && deque[0] <= i - k) deque.shift();
// 2. Maintain decreasing order: pop smaller elements from back
while (deque.length && nums[deque.at(-1)] <= nums[i]) deque.pop();
// 3. Add current index
deque.push(i);
// 4. Window is full — record answer
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}
// For MINIMUM: flip the comparison in step 2 to >=
// while (deque.length && nums[deque.at(-1)] >= nums[i]) deque.pop();Worked Problems
frame
Monotonic deque vs monotonic stack:
- Stack: single end, used for "next greater/smaller element"
- Deque: both ends, used for "window max/min" (evict old from front, maintain order from back)
Pattern recognition:
- "Sliding window max/min" → deque, O(n)
- "DP where dp[i] = f(max dp[j]) for j in window" → deque DP optimization
- Two deques (one max, one min) → control window by range constraint
Implementation: Use array as deque: push/pop from back, shift from front (or pointer-based for O(1) shift).
- Stack: single end, used for "next greater/smaller element"
- Deque: both ends, used for "window max/min" (evict old from front, maintain order from back)
Pattern recognition:
- "Sliding window max/min" → deque, O(n)
- "DP where dp[i] = f(max dp[j]) for j in window" → deque DP optimization
- Two deques (one max, one min) → control window by range constraint
Implementation: Use array as deque: push/pop from back, shift from front (or pointer-based for O(1) shift).