Sliding Window Maximum

Problem

A streaming sensor system processes readings in a fixed-size rolling window and needs the peak reading for each window position in real time. Given an integer array and window size k, return an array of the maximum value in each contiguous window of size k. The window slides one position right at each step.

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3  → [3, 3, 5, 5, 6, 7]
Input: nums = [1],                          k = 1  → [1]
Input: nums = [1, -1],                      k = 1  → [1, -1]

Solution

Approach: Fixed window backed by a monotonic decreasing deque of indices.

A naive scan rechecks all k elements per window at O(n * k); the deque keeps the window maximum in O(1) per step. The deque stores indices, not values, and is kept so that the values at those indices strictly decrease from front to back - meaning the front index always holds the current window maximum. For each end, do three things. First, evict the front if it has slid out of the window: while dq and dq[0] <= end - k: dq.popleft(). Second, evict from the back every index whose value is no greater than nums[end] (while dq and nums[dq[-1]] <= nums[end]: dq.pop()) - those elements can never be the maximum again because a newer, larger-or-equal element now dominates them. Third, append end. Once end >= k - 1 the first full window exists, so record nums[dq[0]].

Storing indices is what makes the front-expiry check possible (dq[0] <= end - k compares positions). Each index is appended exactly once and popped at most once, so total deque work is linear despite the inner whiles.

Trace [1,3,-1,-3,5,3,6,7], k=3: after the third element the deque front points at 3 -> output 3; when 5 arrives it dominates everything, clearing the deque -> output 5, and so on giving [3,3,5,5,6,7].

Edge cases: k = 1 makes every element its own window, so the output equals the input. The deque is never empty when read - the current end was just appended.

Complexity: O(n) time, O(k) space - each index is pushed and popped at most once; the deque holds at most k indices at a time.