Lesson 10.3 · Queue, Deque and Monotonic Queue
Deques and the Monotonic Deque
Keep window candidates in decreasing order: drop expired ones from the front and hopeless ones from the back. The front is always the window's maximum.
16 min
Think of it like this
A cricket team picking its best batter for each 3-match stretch. When a better batter joins, older batters who are worse can never be the best again while the new one is around, so they're dropped from the shortlist. Batters whose stretch has passed retire from the front.
1.Two kinds of removal
From the back: before adding index i, remove indexes whose values are ≤ nums[i]. They're older and not bigger, so they can never be the maximum of any future window that contains i.
From the front: remove the index that has slid out of the window (i − k).
What's left is decreasing from front to back, so the front is the maximum. Each index is added once and removed once: O(n).
nums = [1, 3, -1, -3, 5, 3, 6, 7]deque (front → back)(queue)
maxima(list)
Step 1/43 removed 1 from the back; −1 is kept behind 3. Window [0..2] max: 3.
Remember
- Back: pop values ≤ the newcomer.
- Front: pop the index that left the window.
- Front holds the maximum; O(n) total.
Common mistakes
- Storing values instead of indexes (can't tell when they expire).
- Expiring with
<instead of<=oni − k.