How do you find the maximum value in every window of a given size?
You use a deque that holds the values of the window in decreasing order, and you keep only the values that could still be the answer later.
from collections import deque
def window_max(values, k):
window = deque()
result = []
for i, value in enumerate(values):
# Take out the values that the new value beats.
while window and values[window[-1]] <= value:
window.pop()
window.append(i)
# Take out the values that are outside the window.
if window[0] <= i - k:
window.popleft()
if i >= k - 1:
result.append(values[window[0]])
return result
So how does it work? The deque holds the positions of the values that are still in the window, and the values are in decreasing order from the front to the back. The front always holds the maximum of the window.
And there are two things that you remove. First, when a new value arrives it beats every value at the back of the deque that is smaller than it. Those values can never be the answer again, because the new value is bigger and it stays in the window for longer. So they come off the back.
Second, any position that has fallen out of the window comes off the front. The check window[0] <= i - k asks whether the front position is outside the last k positions.
the values the window of 3 the maximum
------------ ---------------- ----------
[1, 3, -1, -3, 5, 3, 6, 7] [1, 3, -1] 3
[1, 3, -1, -3, 5, 3, 6, 7] [3, -1, -3] 3
[1, 3, -1, -3, 5, 3, 6, 7] [-1, -3, 5] 5
And the complexity is O of n for the time, because each position goes into the deque once and comes out once, and O of k for the space, because the deque never holds more than k positions.
And why is the deque better than a heap? A heap would give you the maximum in O of log k for each window, so the whole thing would be O of n log k. The deque gives you the maximum in O of 1 because the answer is always at the front.
So the rule to remember is this. Keep the window in decreasing order and the maximum is always at the front.
The next two questions in this topic show the simple version and the version for a window that can change.