Sliding Window Maximum
Return the maximum of every window of size k as it slides across the array.
Intuition
Inside a window, any element smaller than a later element can never be a maximum again — discard it forever. A deque of indices with decreasing values keeps only viable champions: front is the max, back absorbs newcomers.
A monotonic deque is for when you need the max or min of a moving window and a heap's lazy deletion feels clumsy. The insight is that if a newer element is bigger than an older one, the older one can never be the answer again — it's dominated for the rest of time. Discard it permanently, and the deque stays sorted so the front is always the answer. Each index is pushed and popped once, giving O(n).
Approach
Monotonic deque invariant
Values at deque indices strictly decrease front-to-back. New element pops smaller ones from the back — they're dominated.
Expire from the front
If the front index slides out of the window (i − k), pop it from the front. Both ends O(1) — hence a deque.
Emit per slide
From i ≥ k−1, the front index's value is the window max. Each index enters and leaves the deque once → O(n).
Solution & live demo
Common pitfalls
Storing values instead of indices
while dq and dq[-1] <= x:
dq.pop()
dq.append(x)while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)Expiry is positional — you need to know when the front entered to know when it slides out of the window. With bare values you can't tell an old 5 from a fresh one. Store indices and dereference through nums for comparisons.
Popping with < and leaving duplicates
while dq and nums[dq[-1]] < x:
dq.pop()while dq and nums[dq[-1]] <= x:
dq.pop()Equal values pile up in the deque, and although the maximum stays correct, the stale copies survive past their expiry and bloat the structure. The newer index dominates an equal older one in every future window, so evict it.
Emitting before the first window is full
res.append(nums[dq[0]])
if i >= k - 1:
res.append(nums[dq[0]])The first complete window only exists once you've consumed k elements. Emitting from index 0 produces k - 1 extra leading answers computed over partial windows.
Edge cases
Deque holds only the current index; output = input.
Nothing pops from the back; front expiry does all the work.