给定一个数组 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
提示：
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
1. 直接使用遍历+内置 api
这个解法在执行测试用例的时候是能通过的，自己写了很多测试用例试了试，但是就是有个问题，时间复杂度为 O(n^2)级别，直接提交的时候执行超时。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
let arr = [];
for(let i = 0; i < nums.length - k + 1; i++) {
arr.push(Math.max(...nums.slice(i, i + k)))
}
return arr;
};
2. 不用内置 api, 直接暴力解法
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
let n = nums.length;
if(n == 0) return [];
let res = [];
for(let i = 0;i < n - k + 1;i++){
let max = Number.MIN_SAFE_INTEGER;
for(let j = i;j < i + k;j++){
max = Math.max(max,nums[j]);
}
res.push(max);
}
return res;
};
3. 使用双端队列
解题思路：使用一个双端队列存储窗口中值的索引，并且保证双端队列中第一个元素永远是最大值，那么只需要遍历一次 nums，就可以取到每次移动时候的最大值。
- 比较当前元素
i和双端队列的第一个元素（索引值），相差 >= k 的时候队首出列。 - 依次比较双端队列的队尾与当前元素 i 对应的值，队尾元素值较小时出列，直至不小于当前元素 i 的值时，或者队列为空，这是为了保证当队头出队时，新的队头依旧是最大值
- 当前元素入队
- 从第 K 次遍历开始，依次把最大值（双端队列的队头）添加到结果
result中
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const deque=[]; //存放单调队列的下标
const result=[];
for(let i=0;i<nums.length;i++){
if(i-deque[0]>=k) deque.shift(); //在滑动窗口之外的直接从队头删掉
while(nums[deque[deque.length-1]]<=nums[i]){
deque.pop(); //如果新加进来的数比单调队列中原来的数都要大，则直接弹出队列中的其他数
}
deque.push(i);
//数组下标从0开始，k=3时 ，下标为0，1，2的数组元素构成一个滑动窗口，所以条件为i>=k-1就可以将答案存入res中
if(i>=k-1) {
result.push(nums[deque[0]]);
}
}
return result;
};