Window Maximums
Problem
A window of fixed width k slides across a list of integers, one position at a time, from the far left to the far right. Report the maximum value inside the window at every stop. The output therefore holds one number for each window position.
Examples
Input: nums = [1, 4, 2, 7, 3, 3], k = 3
Output: [4, 7, 7, 7]
Why: the windows are 1,4,2 then 4,2,7 then 2,7,3 then 7,3,3Input: nums = [5, 5, 5], k = 1
Output: [5, 5, 5]
Why: edge case, a width of one makes every element its own maximumInput: nums = [2, 1], k = 2
Output: [2]
Why: the window covers the whole list, so there is a single stopHints
0 / 3
Rescanning each window costs k work per stop. Notice that consecutive windows overlap heavily, so most of that work repeats an answer you already knew.
Some elements can never be the answer again: any value that is smaller than a newer value to its right is permanently overshadowed. A structure that can drop items from both ends fits that observation.
Keep positions in a double-ended queue ordered so their values decrease from front to back. Before adding a new position, discard positions at the back whose values are not larger, and discard the front once it falls outside the window. The front position always holds the current maximum.
Solution
A double-ended queue stores positions whose values decrease from front to back, which makes the front position the current maximum by construction. A new element evicts every smaller value at the back, because those can never win again while the newer, larger one is in range. The front is dropped as soon as it slides out of the window. Each position is pushed and popped at most once, so time is O(n) and space is O(k).
from collections import deque
def window_maximums(nums, k):
out, dq = [], deque() # dq holds positions, values decreasing
for i, x in enumerate(nums):
if dq and dq[0] <= i - k: # the front just slid out of the window
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop() # smaller older values can never win again
dq.append(i)
if i >= k - 1: # the first full window ends here
out.append(nums[dq[0]])
return out
print(window_maximums([1, 4, 2, 7, 3, 3], 3)) # -> [4, 7, 7, 7]
print(window_maximums([5, 5, 5], 1)) # -> [5, 5, 5]
print(window_maximums([2, 1], 2)) # -> [2]Stuck on the idea rather than the code? Monotonic Stack covers it.