单调队列
解题思路
如何在每次窗口滑动后，将
获取窗口内最大值的时间复杂度从O(k)降低至O(1)；可以维护一个单调递减的双端队列，这个队列里面记录窗口内元素的递减序列，队首就是窗口的最大值；
窗口滑动的过程中，要判断滑出窗口的元素是否在 单调递减队列 里面，如果在里面，需要移除；
图解
复杂度
-
时间复杂度
O(n)： 其中 n 为数组 nums 长度；线性遍历 nums 占用O(n)；每个元素最多仅入队和出队一次，因此单调队列 queue 占用O(2n)； -
空间复杂度
O(k)： 双端队列 queue 中最多同时存储 k 个元素（即窗口大小）；
代码实现
var maxSlidingWindow = function (nums, k) {
const res = [];
const queue = []; // 存储索引
for (let i = 0; i < nums.length; i++) {
// 1. 入，维护单调递减队列
while (queue.length && nums[queue[queue.length - 1]] <= nums[i]) {
queue.pop();
}
queue.push(i);
// 2. 出，只统计窗口内的最大值，窗口不包含队首元素，队首出队
if (i - queue[0] >= k) {
queue.shift();
}
// 3. i >= k - 1 才会形成窗口，记录答案，由于队首到队尾单调递减，所以窗口最大值就是队首
if (i >= k - 1) {
res.push(nums[queue[0]]);
}
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 641. 设计循环双端队列
上一篇
评论
