Sliding Window Maximum
Stacks & Queues: lesson 7 of 9
A queue that drops anyone it has already outgrown.
Lesson 7 of 9 · 6 min
Sliding Window Maximum
Step 1 of 10
k3front—
nums
i
1
3
-1
-3
5
3
deque — indexes, values decreasing
1
3
-1
-3
5
3
window maxima
3
3
5
5
Every window of 3 needs its maximum. Recomputing each one costs O(nk) — the deque gets it in one pass.
The Idea
Recomputing the maximum for every window costs O(nk). Instead hold a deque of indexes whose values decrease from front to back.
A new value pops every smaller one from the back — they are older and weaker, so they are finished. The front expires when it leaves the window. The front is always the answer.
Real-World Example
A shop's rolling record for "best offer in the last seven days". A better offer today retires every worse one still on the board, and yesterday's leader drops off only when it ages out.
The Code
from collections import deque
def window_max(nums, k):
dq, out = deque(), [] # dq holds indexes, their values decreasing
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # smaller and older than x: never the max again
dq.append(i)
if dq[0] == i - k: dq.popleft() # the front just slid out of the window
if i >= k - 1: out.append(nums[dq[0]])
return out
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)) # [3, 3, 5, 5, 6, 7]Your turn
Put the steps in the right order.
- Once the window is full, read the front of the deque as this window's maximum
- Push the new index onto the back
- Pop every index at the back whose value is at most the new value
- Drop the front index if it has just slid out of the window
Mini quiz
1 / 3