Sliding Window Maximum
A monotonic deque of indices keeps the window maximum at the front in amortized O(1).
3 enters. The back of the deque is 1, which is not larger than 3 and will leave the window sooner. It can never be the maximum again, so pop it.
What you will see
The window slides; the deque drops dominated values from the back and expired ones from the front.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(k) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Items announce position from the top or front and value; each step announces the operation and the new top or front.
Reduced motion: Items appear or disappear in place with a crossfade instead of sliding in or out.
Before this
Related
Taught by the same lesson
Sliding Window Maximum covers these too, in the same run.