Array - 239. Sliding Window Maximum
- Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the _k_numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Note
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.
Follow up:
Could you solve it in linear time?
Solution Approach:
-
Input Validation:
- First, handle the edge cases by checking if the input array
nums
is null or ifk
is less or equal to 0. If so, return an empty array.
- First, handle the edge cases by checking if the input array
-
Initialization:
- Initialize a result array
res
of size(len - k + 1)
to store the maximum values of each window. - Initialize an index variable
index
to 0, which will be used to populate the result array. - Initialize a deque
deque
to help in keeping track of the maximum element in the current window.
- Initialize a result array
-
Iterate Through the Array:
- Iterate through the input array
nums
using a loop variablei
. - In each iteration, perform the following steps:
- Clean Up Deque:
- Remove the first element from the deque if it is outside the current window (i.e., its index is less than
i - k + 1
). - Remove the last element from the deque if it is less than the current element, to maintain the deque in a decreasing order.
- Remove the first element from the deque if it is outside the current window (i.e., its index is less than
- Update Deque:
- Add the current element’s index
i
to the deque.
- Add the current element’s index
- Populate Result Array:
- If
i
is greater or equal tok - 1
, it means the deque hask
elements. Therefore, add the maximum element of the current window (which is at the front of the deque) to the result array.
- If
- Clean Up Deque:
- Iterate through the input array
-
Return the Result:
- After the loop, return the result array
res
which now contains the maximum values of all sliding windows of sizek
.
- After the loop, return the result array
This algorithm efficiently keeps track of the maximum element in each window of size k
as it slides through the input array, using a deque to ensure a time complexity of O(n).
Code:
java:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0 ) return new int[]{};
int len = nums.length;
int[] res = new int[len - k + 1];
int index = 0;
Deque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < len; i++){
// Pop the first index from the deque if the deque size exceeds k.
while(!deque.isEmpty() && deque.peek() < i - k +1) deque.poll();
// Pop the last index from the deque to maintain monotonic(decreasing order).
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
// Add current index to deque end
deque.offer(i);
// Since i starts from 0, we must wait until the queue size is k to start populating the result array.
if (i >= k-1) {
res[index++] = nums[deque.peek()];
}
}
return res;
}
}