239.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.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
1 | Window position Max |
Therefore, return the max sliding window as [3,3,5,5,6,7].
O(n log k) O(k) space heap solution
1 | public class Solution { |
O(n) time O(k) space deque solution
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length < 1) return new int[0];
int[] res = new int[nums.length - k + 1];
int resIndex = 0;
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
if (i >= k - 1) {
res[resIndex++] = nums[deque.peek()];
}
}
return res;
}
}