A window of size k slides over the array one step at a time. Return the maximum of every window.
DSA Animator › DSA Revision › Queue › Sliding Window Maximum
Remember: a monotonic deque keeps candidates in decreasing order. Smaller values behind a bigger, newer one can never win. The video solves Sliding Window Maximum (LeetCode 239, Hard) with the Monotonic Deque pattern from the Queue topic, and you can replay every step in the interactive Sliding Window Maximum animation.
A window of size k slides over the array one step at a time. Return the maximum of every window.
For 1, 3, minus 1, minus 3, 5, 3, 6, 7 with k equal to 3, the maximums are 3, 3, 5, 5, 6, 7.
Scanning every window for its maximum is O of n times k. A heap works in O of n log n, but a deque does it in linear time.
Keep a deque of indexes whose values are decreasing from front to back. Before adding a new number, pop smaller values from the back, because they can never be a maximum again. Pop the front if it has slid out of the window. The front is always the maximum of the current window.
1 enters, then 3 pushes 1 out, because 1 can never win again. Minus 1 is smaller, so it waits behind 3, and the first window maximum is 3. Minus 3 joins the back, and the maximum is still 3. 5 clears everything smaller, and the maximum is 5. 3 waits behind 5, so the maximum stays 5. 6 clears the deque, and the maximum is 6. 7 clears it again, and the last maximum is 7. The answer is 3, 3, 5, 5, 6, 7.
In code, for each index, drop the front if it is out of the window. Drop indexes from the back while their values are smaller than the new one, then add the new index. Once the first window is complete, the front gives the answer. Each index enters and leaves once, so it's O of n time and O of k space.
Remember: a monotonic deque keeps candidates in decreasing order. Smaller values behind a bigger, newer one can never win.