Hard Monotonic Deque Sliding Window
In plain English: As a window of size k slides across the array, report the biggest number in each window position.
A monotonic decreasing deque keeps the current max at the front. When sliding right, pop smaller elements from the back (they can never be the max). Pop from the front when elements leave the window.
Prompt
Given an array nums and a sliding window of size k moving left to right, return the maximum value in each window position.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values are decreasing
result = []
for i, num in enumerate(nums):
# remove elements outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# maintain decreasing order
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Test: max_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]