剑指 Offer 59 - I. 滑动窗口的最大值
同 239. 滑动窗口最大值
单调队列
用双端队列保存有可能是滑动窗口最大值的数字的下标。
在存入一个数字的下标之前，先判断队列里已有数字是否小于待存入的数字，若是，则这些数字不可能是滑动窗口最大值，将它们依次从队尾删除。
此时，队头元素为滑动窗口最大值。
如果队头元素已经从窗口滑出，则将滑出的数字从队头删除。
因为队头和队尾都有可能删除数字，所以需要使用双端队列。
因为队列中元素满足严格单调递减，所以这种单调性的队列一般称作单调队列。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
// 双端队列
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
res[0] = nums[deque.peekFirst()];
for (int i = k; i < nums.length; i++) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst(); // 将窗口最左侧元素移出队列
}
deque.offerLast(i); // 窗口向右移动一个位置，将新元素加入队列
res[i - k + 1] = nums[deque.peekFirst()];
}
return res;
}
}
- 时间复杂度：O(n) ，n 是数组 nums 的长度，每一个下标恰好被放入队列一次，并且最多被弹出队列一次。
- 空间复杂度：O(k) ，双端队列最多同时存储 k（窗口大小）个元素。
