日拱算法，滑动窗口的最大值_安东尼漫长的技术岁月的技术博客_51CTO博客
source link: https://blog.51cto.com/u_13961087/5693331
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
日拱算法，滑动窗口的最大值
精选 原创日拱算法，接着冲~~
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[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
题目来源： 剑指 Offer 59 - I. 滑动窗口的最大值
有时候搞不太懂力扣对于难度等级的判定，此题为“困难”？
用长度为 k 的数组去遍历 nums 就可以了，每次拿到它的最大值，然后push进结果数组中，再返回不就行了？
分步解析：
1.找到窗口从头滑到尾需要滑动的次数为： nums.length - k + 1；
2.初始化队列；
3.每次滑动的时候，找到当前窗口的最大值保存到 res 数组，然后执行删除队列头元素、在队列尾添加下一元素的操作；
JavaScript 实现：
if (nums.length == 0 || k > nums.length) return []
var index = k
var len = nums.length - k + 1
var stack = [], res = []
for (var j = 0; j < k; j++) {
stack.push(nums[j])
}
for (i = 0; i < len; i++) {
if (i !== 0) {
stack.shift()
stack.push(nums[index])
index++
}
res.push(Math.max.apply(null, stack))
}
return res
};
提交看看，结果报错“超出时间限制” QAQ
噢噢，再回看算法，for 循环里面要对数组一整个 Math.max，时间复杂度肯定爆表了，O(n\*n)，不超时才怪。
正解：转换思路 采用单调数列
依次将数组的下标push到窗口中，超出窗口的shift掉，窗口是个单调递减队列，队头元素就是当前窗口的最大值；
步骤拆解：
1、每当读入的数大于队尾，则循环删除队尾小于读入元素的数字，保证队列的递减单调性
2、如果单调的队首（极大值），等于窗口左边界的上一位，则说明极大值已经超出窗口，移除单调递减队列的队首
3、每次窗口滑动的最大值为，单调递减队列的队首
4、循环以上步骤，直到窗口的右边界到队尾
JS 实现：
const res = []; //保存滑动窗口的最大值
const q = []; //滑动窗口队列
for (let i = 0; i < nums.length; i++) {
//1.在队尾添加元素num[i]
var last = q.length - 1; //队列的最后一个元素的索引
while (last >= 0 && nums[i] > q[last]) { //2.循环求解序列中的最大值
//2.求队列中的最大值：如果新入队列的元素，比队尾元素大，队尾被更新成新入队列的元素,保证队头为队列中的最大元素
q.pop(); //队尾移除，
last = q.length - 1; //队列更新长度
}
q.push(nums[i]); //入队列
// 当窗口i + 1 - k >= 0时，窗口满了有三个数了
const j = i + 1 - k; //窗口向右滑动过程中最后一个元素的索引。
if (j >= 0) {
res.push(q[0]); //保存每一次k个窗口的最大值
if (nums[j] === q[0]) { //3.向有滑动过程中，如果序列中的最大元素即退出窗口，则移除队列头部元素
q.shift(); //
}
}
}
return res;
};
小结：除了以上两种解法，还有其它思路，不得不说这题还是很有学问的。在处理滑动窗口问题中，经常会遇到要构造一个单调队列，得着重记笔记记笔记。(ಥ﹏ಥ)
OK，以上便是本篇分享。点赞关注评论，为好文助力👍
我是掘金安东尼 🤠 100 万人气前端技术博主 💥 INFP 写作人格坚持 1000 日更文 ✍ 关注我，安东尼陪你一起度过漫长编程岁月 🌏
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK