写点什么

LeetCode 题解:239. 滑动窗口最大值,单调队列,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 09 月 06 日
LeetCode题解:239. 滑动窗口最大值,单调队列,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/sliding-window-maximum/



解题思路:



参考了【视频解析】 双端队列滑动窗口最大值、[Intuitive JavaScript Solution with Monotonic Queue](https://leetcode.com/problems/sliding-window-maximum/discuss/585149/Intuitive-JavaScript-Solution-with-Monotonic-Queue)



  1. 每次滑动窗口时,将移出窗口的值移除队列

  2. 将新进入窗口的值存入队列,同时将队列中比移入值小的元素都移除,这个操作会保证队列都是从大到小排列。

  3. 队列的第一个值始终是当前窗口中最大值,每次循环将其存入结果数组即可。



/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let result = [];
let dequeue = [];
for (let i = 0; i < nums.length; i++) {
// 当窗口滑动时,检查队列最前端元素是否不在窗口中,若是则将其移除
if (nums[i - k] === dequeue[0]) {
dequeue.shift();
}
// 如果队列中有值,则将队列中比当前值小的值全部清空。保证队列从大到小排列。
while (dequeue.length && nums[i] > dequeue[dequeue.length - 1]) {
dequeue.pop();
}
// 将新进入窗口的值存入队列。
dequeue.push(nums[i]);
// 当窗口被填满后,才开始存储结果
if (i >= k - 1) {
// 当前队列第一个值始终是当前滑块最大值,可直接存入结果
result.push(dequeue[0]);
}
}
return result;
};



发布于: 2020 年 09 月 06 日阅读数: 57
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:239. 滑动窗口最大值,单调队列,JavaScript,详细注释