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;};
