The tell: Maximum of every fixed-size window, with a linear-time requirement.
How you get there
1Keep a deque of indices whose values are strictly decreasing.
2Before pushing i, pop every index whose value is smaller — they can never be a future maximum.
3Pop from the front once it falls outside the window; the front is always the answer.
Solution
Python
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
dq: deque[int] = deque() # indices, values decreasing
out: list[int] = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] < x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # front has left the window
if i >= k - 1:
out.append(nums[dq[0]])
return out
Time
O(n)
Space
O(k)
What goes wrong
Storing values rather than indices makes it impossible to tell when the front leaves the window.