Sliding Window Maximum
Hard · rating 1800 · Queue
The first line has n and k. The second line has n integers. For every contiguous window of size k, print its maximum; output the n-k+1 results space-separated.
Constraints: 1 ≤ k ≤ n ≤ 105
Editorial
Approach
Keep a deque of indices whose values are in decreasing order — the front is always the current window's maximum. Before adding a new index, pop smaller values off the back (they can never be a max while the newcomer is around); drop the front if it has slid out of the window.
Why it's linear
Each index enters and leaves the deque at most once, so the total work is O(n) even though every window is queried.
for i in range(n):
while dq and a[dq[-1]] <= a[i]: dq.pop()
dq.append(i)
if dq[0] <= i - k: dq.popleft()
if i >= k-1: out.append(a[dq[0]])Complexity
Time: O(n). Space: O(k).