You are given an array of integers 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.
Test Cases
Input:
(int[]) nums = [1,3,-1,-3,5,3,6,7]
(int) k = 3
Output:
(int[]) [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
Input:
(int[]) nums = [1]
(int) k = 1
Output:
(int[]) [1]
Solution
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) {
return new int[0];
}
int[] result = new int[n - k + 1]; // number of windows
Deque<Integer> win = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; ++i) {
// remove indices that are out of bound
while (win.size() > 0 && win.peekFirst() <= i - k) {
win.pollFirst();
}
// remove indices whose corresponding values are less than nums[i]
while (win.size() > 0 && nums[win.peekLast()] < nums[i]) {
win.pollLast();
}
// add nums[i]
win.offerLast(i);
// add to result
if (i >= k - 1) {
result[i - k + 1] = nums[win.peekFirst()];
}
}
return result;
}
}from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if n == 0 or k == 0:
return []
res, window = [0]*(n-k+1), []
for i in range(n):
while window and window[0] <= i-k:
window.pop(0)
while window and nums[window[-1]] < nums[i]:
window.pop()
window.append(i)
if i >= k - 1:
res[i-k+1] = nums[window[0]]
return res