Sliding Window Maximum
Explanation & Solution
Description
Given an array of integers nums and an integer k representing the size of a sliding window, the window moves from the very left to the very right of the array. Each time the window moves one position to the right, return the maximum value in the current window.
Return an array of the maximum values for each window position.
Examples
Explanation:
- Window [1,3,-1] → max = 3
- Window [3,-1,-3] → max = 3
- Window [-1,-3,5] → max = 5
- Window [-3,5,3] → max = 5
- Window [5,3,6] → max = 6
- Window [3,6,7] → max = 7
Explanation: Only one window of size 1, which contains just the element 1.
Explanation: Each element is its own window of size 1.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
Approach
Sliding Window pattern
1. Initialize a Monotonic Deque
Create a deque (double-ended queue) that stores indices of elements. The deque maintains a monotonic decreasing order by value — the front always holds the index of the largest element in the current window.
2. Remove Out-of-Window Indices
As the window slides, check if the front of the deque is outside the current window boundary (i - k + 1). If so, remove it from the front.
3. Maintain Monotonic Order
Before adding the current index i, remove all indices from the back of the deque whose corresponding values are less than or equal to nums[i]. These elements can never be the maximum for any future window since nums[i] is both larger and more recent.
4. Add Current Index
Push the current index i onto the back of the deque.
5. Record the Window Maximum
Once the window is fully formed (i >= k - 1), the front of the deque holds the index of the maximum element in the current window. Add nums[deque[0]] to the result array.
6. Return the Result
After processing all elements, return the result array containing the maximum of each window.
Key Insight
The monotonic deque ensures that the front always holds the index of the current window's maximum. Each element is pushed and popped from the deque at most once, giving an O(n) time complexity — far better than the naive O(n*k) approach of scanning each window.
Visualization
Press ▶ or use ← → to step through