visual walkthrough
Sliding Window Maximum
Introduces the monotonic deque for O(n) window maxima.
The idea
Keep a deque of candidate maxima. When a new number arrives, any smaller numbers at the back can never be a maximum again (the new one is bigger and will stay in the window longer), so remove them.
That keeps the deque in decreasing order, so the front is always the maximum. Each number enters and leaves the deque once.
Complexity
| approach | time | space |
|---|---|---|
| Scan every window | O(n · k) | O(1) |
| Monotonic deque | O(n) | O(k) |