Practice: Sliding Window Maximum
A deque of candidates.
Slide a window of size K across a list, and report the largest number in every window. Checking every window from scratch costs O of N times K. We can do it in O of N, with a deque.

- A window of size k
- The max of every window
- O(n) with a deque
Keep only useful candidates
The deque holds positions, with their values in decreasing order. When a new number arrives, any smaller numbers behind it can never be the maximum again, so we pop them. If the front has slid out of the window, we drop it. The front is always the window's maximum. Run it.
from collections import deque
def window_max(nums, k):
q, out = deque(), []
for i, x in enumerate(nums):
while q and nums[q[-1]] <= x:
q.pop()
q.append(i)
if q[0] <= i - k:
q.popleft()
if i >= k - 1:
out.append(nums[q[0]])
return out
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))[3, 3, 5, 5, 6, 7]
A monotonic deque
A deque kept in sorted order like this is called a monotonic queue. Each position is added once and removed at most once, so the whole thing is O of N, even with the inner while loop. The same idea finds the next greater element, and daily temperatures.
| key | value |
|---|---|
| Deque holds | positions, values decreasing |
| New number | pops smaller ones |
| Front | the window max |
| Cost | O(n) |
Summary
Keep a deque of candidates in decreasing order, and the front is always the maximum. Each item enters and leaves once. Next, splitting a string into words.
Key takeaways- Pop smaller from the back
- Drop old from the front
- Front is the max