Leetcode第239题 滑动窗口的最大值
思路
使用单调队列,如果新进来的数字大于滑动窗口的末尾元素,那么末尾元素就不可能再成为窗口中最大的元素了,因为这个大的数字是后进来的,一定会比之前先进入窗口的小的数字要晚离开窗口,因此我们就可以将滑动窗口中比其小的数字弹出队列。
var maxSlidingWindow = function (nums, k) {
const len = nums.length;
//下标递增,值递减的队列
const q = [];
const ans = [];
for (let i = 0; i < len; i++) {
//删除出界的选项
while (q[0] <= i - k) {
q.shift();
}
//插入新选项i,维护单调性(值递减)
while (q.length && nums[i] > nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
//取队头更新答案
if (i >= k - 1) {
ans.push(nums[q[0]]);
}
}
return ans;
};