Sliding Window Maximum
Return the maximum of every window of size k as it slides across the array.
02
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.
03
Approach
1
Monotonic deque invariant
Values at deque indices strictly decrease front-to-back. New element pops smaller ones from the back — they're dominated.
2
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.
3
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).
04
Solution & live demo
python
▶1from collections import deque
▶2
▶3class Solution:
▶4 def maxSlidingWindow(self, nums, k):
▶5 dq, res = deque(), [] # dq: indices, values decreasing
▶6 for i, x in enumerate(nums):
▶7 while dq and nums[dq[-1]] <= x:
▶8 dq.pop() # dominated forever
▶9 dq.append(i)
▶10 if dq[0] == i - k:
▶11 dq.popleft() # slid out of window
▶12 if i >= k - 1:
▶13 res.append(nums[dq[0]])
▶14 return res
05
Edge cases
k = 1
Deque holds only the current index; output = input.
Monotone decreasing input
Nothing pops from the back; front expiry does all the work.
06
Complexity
Time
O(n)
Space
O(k)
Each index pushed/popped at most once per end.