The sliding window maximum
You slide a fixed width window across an array and want the maximum inside it at every step. Rescanning the window each time is slow. A monotonic deque keeps the answer ready as the window moves.
A deque that stays ordered
Maintain a double ended queue of candidate indices whose values are decreasing from front to back. As a new element enters on the right:
- Pop from the back every candidate smaller than the new element, since they can never again be the maximum while the newcomer is present.
- Push the new index at the back.
As the window's left edge advances, pop from the front any index that has fallen out of the window. The front of the deque is always the index of the current window maximum.
Why it is efficient
Each index is pushed once and popped once across the whole scan, so although a single step may pop several items, the total work is proportional to the array length. The same structure tracks a sliding minimum by keeping the deque increasing instead.
Key idea
Keep a deque of indices with decreasing values so the front is always the window maximum, with each index entering and leaving once.