#239
Sliding Window Maximum
Hard Monotonic deque
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For every window of size k sliding across the array, return the maximum.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the maximum of every window of size k.
Why this works: a deque of indexes with decreasing values. The front is the max; drop it when it leaves the window, and drop smaller values from the back.
Example: [1, 3, -1, -3, 5, 3, 6, 7], k = 3
maxima: 3, 3, 5, 5, 6, 7✦Hints open one at a time
A heap works in O(n log n). Can you do O(n)?
Keep a deque of indexes whose values are decreasing from front to back.
The front is the current maximum; drop it when it leaves the window.
↗Approach
For each i: remove the front if it's out of the window (i − k). Remove from the back while the back's value <= nums[i] — those can never be a maximum again. Add i. Once i >= k − 1, record nums[front].
</>Solution (Java)
import java.util.*;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // indexes, values decreasing
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // left the window
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // useless now
dq.offerLast(i);
if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}
}!Common mistake
Storing values instead of indexes, so you can't tell when the front has left the window.
Complexity
- Time: O(n).
- Space: O(k).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon