Problem
Given an integer array nums and an integer k, return an array containing the maximum value from each sliding window of size k.The window moves one position to the right at a time until it reaches the end of the array.
Example
Consider the following example to understand the expected input and output.Input
nums = [1,3,-1,-3,5,3,6,7]
k = 3Output
[3,3,5,5,6,7]Solution
This solution uses the Sliding Window technique along with a Deque to efficiently keep track of the maximum value in the current window.The deque stores the indices of elements in decreasing order of their values. The element at the front of the deque is therefore always the maximum value in the current window.
For every new element, we first remove indices from the front that are outside the current window. We then remove indices from the back while their corresponding values are smaller than the current value because they can no longer become the maximum while the current element remains in the window.
Once the window reaches size k, the value at the front of the deque is the maximum for that window.
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int right = 0; right < n; right++) {
// Remove indices outside the current window.
while (!deque.isEmpty() && deque.peekFirst() < right - k + 1) {
deque.pollFirst();
}
// Remove smaller values from the back.
while (!deque.isEmpty()
&& nums[deque.peekLast()] <= nums[right]) {
deque.pollLast();
}
deque.offerLast(right);
// Store the maximum once the window reaches size k.
if (right >= k - 1) {
result[right - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}Complexity
Each array index is added to the Deque once and removed at most once. Therefore, the overall time complexity is O(n).The deque can contain at most k indices, so the extra space complexity is O(k).
