# 题目
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 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
# 思路
用一个双端队列window来存储滑动窗口
队列中存储滑动窗口的索引，根据窗口末尾元素和首位元素判断首位元素是否应该被移出队列
当前进入的元素下标 - 窗口头部元素的下标 >= k 头部元素移出队列
当新元素进入队列时，从队列末尾元素开始比较，将比新元素小的元素全部移出队列，这样可以保证队列中首个元素永远是窗口最大值
第k次遍历后开始向结果中添加最大值（滑动窗口首位元素）
时间复杂度O(n)
空间复杂度O(n)
# 代码
function maxInWindows(num, size) {
const window = [];
const result = [];
if (Array.isArray(num) && num.length > 0 && size > 0) {
for (let i = 0; i < num.length; i++) {
if (i - window[0] >= size) {
window.shift();
}
let n = window.length - 1;
while (n >= 0 && num[window[n]] < num[i]) {
n--;
window.pop();
}
window.push(i);
if (i >= size - 1) {
result.push(num[window[0]]);
}
}
}
return result;
}
阅读全文
