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?
Idea 1. Sliding window, borrow the idea of montone increasing queue, moving two pointers.
右边界向右边滑，扫新的元素，
- pop out all nums[j] if nums[right] > nums[j] (j < i), 因为新的数大，窗口中前面的小数不可能是窗口的max value, 形成一个递减的queue, the queue head is the local maximum in the current window;
- push nums[right]
左边界向右边滑，
pop out nums[left] if deque.peekFirst == nums[left], 如果左边界是最大值，向右移左边届已经不在有效窗口内，需要从queue头移除最大值
Since pop operation needed on both ending, deque is a suitable struct.
Time complexity: O(n) since each element is only pushed once and poped out once from the deque.
Space complexity: O(n)
1.a deque store the array item
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k > nums.length) {
return new int[0];
}
Deque<Integer> maxBuffer = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
for(int left = 0, right = 0; right < nums.length; ++right) {
while(!maxBuffer.isEmpty() && nums[right] > maxBuffer.peekLast()) {
maxBuffer.pollLast();
}
maxBuffer.offerLast(nums[right]);
if(right >= k-1) {
result[left] = maxBuffer.peekFirst();
if(nums[left] == result[left]) {
maxBuffer.pollFirst();
}
++left;
}
}
return result;
}
}
python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
maxBuffer = collections.deque() result = []
for right in range(len(nums)):
while maxBuffer and maxBuffer[-1] < nums[right]:
maxBuffer.pop() maxBuffer.append(nums[right])
if right >= k - 1:
result.append(maxBuffer[0]) if maxBuffer[0] == nums[right - k + 1]:
maxBuffer.popleft() return result
1.b deque store the array index, instead,
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k > nums.length) {
return new int[0];
}
int[] result = new int[nums.length - k + 1];
Deque<Integer> maxIndexBuffer = new ArrayDeque();
for(int left = 0, right = 0; right < nums.length; ++right) {
while(!maxIndexBuffer.isEmpty() && nums[maxIndexBuffer.peekLast()] < nums[right] ) {
maxIndexBuffer.pollLast();
}
maxIndexBuffer.offerLast(right);
if(right >= k-1) {
int maxIndex = maxIndexBuffer.peekFirst();
result[left] = nums[maxIndex];
if(maxIndex == left) {
maxIndexBuffer.pollFirst();
}
++left;
}
}
return result;
}
}
python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
maxIndex = collections.deque() result = []
for right in range(len(nums)):
while maxIndex and nums[maxIndex[-1]] < nums[right]:
maxIndex.pop() maxIndex.append(right)
if right >= k - 1:
result.append(nums[maxIndex[0]]) if maxIndex[0] == right - k + 1:
maxIndex.popleft() return result