You are given an integer array nums and a window of size k that slides from the very left of the array to the very right, one position at a time. Return the maximum of each window. Aim for O(n) time.
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]nums = [1], k = 1[1]i: if the front index left the window (≤ i − k), pop it from the front ⌛≤ nums[i], pop it from the back 🗑️ (it can never be a max again)i to the backi ≥ k − 1), the answer is nums[front] 👑Every index is pushed once and popped at most once, so the deque does at most 2n operations in total, no matter how big k is. Checking every window directly costs (n − k + 1) · k comparisons, which is O(n·k). The watch-out: store indices, not values, so you can tell when the front has slid out of the window.
k = 1 → every element is its own max. k = n → one window, one answer. Decreasing array → nothing is ever popped from the back and the deque fills up to k. Duplicates → using ≤ drops the older copy, which is safe because the newer one lasts longer.
Scanning every window for its maximum is O(n) times k. A heap works in O(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.
A monotonic deque keeps candidates in decreasing order. Smaller values behind a bigger, newer one can never win.
Run the animation above on your own input, or watch the 1:40 video explanation of Sliding Window Maximum with a dry run and Java code.