Problem
Given an array and a window size k, return the max in each sliding window.
Example
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]Solution
Monotonic deque. Store indices. Front is always the max of the current window. Pop from back when adding smaller values.
from collections import deque
def max_sliding_window(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k: dq.popleft()
while dq and nums[dq[-1]] < n: dq.pop()
dq.append(i)
if i >= k - 1: result.append(nums[dq[0]])
return resultfunction maxSlidingWindow(nums, k) {
const dq = [];
const result = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length && dq[0] <= i - k) dq.shift();
while (dq.length && nums[dq[dq.length-1]] < nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) result.push_back(nums[dq.front()]);
}
return result;
}public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>();
int[] result = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
dq.offerLast(i);
if (i >= k - 1) result[idx++] = nums[dq.peekFirst()];
}
return result;
}Complexity
- Time: O(n)
- Space: O(k)
Explanation
Deque indices have decreasing values. Smaller values get popped because they’re useless once a larger one arrives. Each element enters and exits the deque once.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?