The sliding window maximum
To report the maximum of every fixed size window as it slides, a naive scan rechecks the whole window each step. A monotonic deque does better by keeping only the elements that could still become a maximum, in decreasing order from front to back.
Maintaining the order
The deque stores indices, and you keep its values monotonically decreasing:
- Push back: before adding a new element, pop from the back every element smaller than it, since they can never be the max while the larger newcomer is in the window.
- Pop front: when the window moves past the index at the front, remove it.
- Read front: the front index always holds the current window maximum.
Why it is efficient
Each index is pushed once and popped once across the entire run, so although a single step may pop several elements, the amortized cost per step is constant. The deque never holds more than one window of indices.
Key idea
A monotonic deque keeps window candidates in decreasing order, popping smaller back elements and stale front ones, so every sliding window maximum is read from the front in amortized constant time.