The biggest in every window
Slide a window along an array and report its maximum each time, using a double-ended queue that keeps only the values that could still win. About 18 minutes.
Throw away the losers
You slide a window of size k and want the biggest value in each position. Keep a deque of positions. Before adding a new value, remove from the back every position whose value is not bigger than the new one.
Those older, smaller values can never win again, because the new value is both bigger and will stay in the window longer. What is left is a list of values falling from front to back.
from collections import deque dq = deque([5, 3, 1]) dq.pop() # remove from the back dq.append(2)
Window 4, 2, 12. The 12 removes the smaller 2 and 4. The deque holds only 12. The maximum is 12.
Expire from the front
A window of size k at position i covers positions i minus k plus 1 up to i. The front of the deque is the oldest position kept, so if it equals i minus k, it has just left the window, and must be removed from the front.
After that, once the window is full, the front is the answer for this window. That is why a deque is needed rather than a stack: you remove from the back for new values and from the front for old ones.
oldest = dq.popleft() # from the front
Why can a smaller older value be removed when a bigger new value arrives?
- AThe new value stays in every window the old one is in, so the old one can never be the maximum
- BThe older value always leaves first
- CThe deque must be sorted by position
Show the answer
The new value stays in every window the old one is in, so the old one can never be the maximum. The new value is bigger and also leaves later.
Sliding window maximum
You are given an array nums and a window size k. The window starts at the left end and moves one position to the right each time. Return the maximum value in the window at each position, once the window is full.
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]
1 ≤ k ≤ length of nums ≤ 100,000 · -10,000 ≤ nums[i] ≤ 10,000