Monotonic Queue
A deque kept sorted so the window maximum is always at the front.
Decision · step 3 of 23Sliding Window Maximum: Maximum of every 3
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
Values that can never be a maximum are dropped from the back as the window slides.
Cost
| push with pops | O(1) amortized |
|---|---|
| pop front | O(1) |
| 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, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Sliding Window Maximum covers these too, in the same run.