239.滑动窗口最大值

描述

给定一个数组 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

代码及思路

思路

其实开始感觉这个题目没啥难度,不知道为啥是困难。(年轻啊0.0)。

说一下最开始的思路:主要利用数组的slice函数来不断获取窗口内的数组,然后利用Math.max.apply(null, windowArr)获取窗口数组的最大值。然后考率一下窗口宽度大于数组长度的情况,即获取整个数组的最大值。

然后就有了下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let len = nums.length;
let res = [];
if (k >= len) return [Math.max.apply(null, nums)];
for (let i = 0; i <= len - k; i++) {
res.push(Math.max.apply(null, nums.slice(i, i + k)));
}
return res;
};

可悲的是:超时啦。(是因为一个巨长的数组引起的)

然后改进了一下,想着既然是因为数组的长度引起的问题,那么就不维护一个那么长的数组啦,只要维护窗口宽度k长度的数组。毕竟是要取窗口宽度内的数组最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
if(nums.length === 1) return nums;
let arr = [], res = [];
for(let i = 0; i < nums.length; i++) {
arr.push(nums[i]);
if(i >= k - 1) {
res.push(Math.max(...arr));
arr.shift();
}
}
return res;
};

这次确实通过啦,但是那个时间7036ms

遂去研究了一下大佬们的代码(如下)

代码

参考代码链接

自己写一个由大到小的有序队列queue,队列里0的位置一直是最大的元素,里面有3个方法:

  • push(val):先将队列里面小于val的数都删掉,然后将val插入到队列;
  • pop(val):用于删除窗口外的最大值(比如你在找3,4,5三个位置的最大值,但是2位置的最大值还在队列里面,而且比它们都大,但是它已经过时了,要把它删掉,不能影响后续的比较),如果最大值还在窗口内那么它不会删除任何值
  • max():返回队列的第一个元素,也就是最大值

双端队列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
class Queue {
constructor() {
this.queue = [];
}
push(val) {
while(this.queue.length && this.queue[this.queue.length - 1] < val) {
this.queue.pop();
}
this.queue.push(val);
}
pop(val) {
if(this.queue[0] === val) this.queue.shift();
}
max() {
return this.queue[0];
}
}

let len = nums.length;
let queue = new Queue();
let res = [];
if(k === 0) return [];
for(let i = 0; i < k - 1; i ++) {
queue.push(nums[i]);
}
for(let i = k - 1; i < len; i ++) {
queue.push(nums[i]);
res.push(queue.max());
queue.pop(nums[i - k + 1]);
}
return res;
};