Report the biggest number in every window of k as it slides. Keep a deque of shrinking values, so the front is always the max.
▼The problem
LeetCode 239 (Hard). Given an integer array nums and a window size k, slide the window from the left end to the right end one position at a time and return the maximum of each window.
Examples (LeetCode's): nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7] and nums = [1], k = 1 → [1].
The solution
from collections import deque
def maxSlidingWindow(nums, k):
dq, out = deque(), []
for i, x in enumerate(nums):
if dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(nums[dq[0]])
return outTranscript
Sliding Window Maximum. Slide a window of size k across a list of numbers and report the biggest number in each window. Each number is a fish, and the window is a porthole.
With one, three, minus one, minus three, five, three, six, seven, and k of three, the six windows give three, three, five, five, six, seven. One fish, one, with k of one, gives one.
Rescanning every window costs k looks per window: order n times k. A heap gets order n log n. We can do better.
Keep a deque of indices whose fish shrink from front to back. For each new fish, drop the front if it left the window. Pop from the back every fish no bigger than the new one: it's smaller and leaves sooner, so it's never the max again. Push the new fish. The front is the max.
In code: pop the front when it falls out of range, pop the back while it's at most the new value, append i, and once the window is full, record the front.
Try the example. One joins, then three eats one. Minus one waits behind three: the first max is three. Minus three joins: still three. Three swims out, and five eats both minus fish: five. Three waits: five. Six eats three and five: six. Seven eats six: seven.
Each index joins once and leaves at most once: order n time. The deque holds at most k: order k space.
Drop the old, eat the small, read the front. That's Sliding Window Maximum.