Sliding Window Maximum
Given an array of integers `nums` and an integer `k`, return the maximum value in each subarray of size `k`.
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= k <= nums.length
Examples:
Input: [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: The maximum values in each subarray of size 3 are 3, 3, 5, 5, 6, 7.
Solutions
Deque
Time: O(n)Space: O(n)
We use a deque to store the indices of the elements in the current window. We remove the elements that are out of the window and the elements that are smaller than the current element from the deque. We then add the current element to the deque. Finally, we add the maximum element in the deque to the result.
import java.util.Deque;
import java.util.LinkedList;
public
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
for (int i = 0;
i < nums.length;
i++) {
while (!deque.isEmpty() && deque.peek()Question and saidQuestion - k + 1) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}Follow-up:
What if the input array is empty or k is larger than the length of the array?
