题目(hard)
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
思路
大顶堆虽然每次都能弹出最大值，但是因为没法弹出其他值，故不适合。
单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：
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
39
40
41
42
43
44
45
| class MonoQueue {
queue;
constructor() {
this.queue = [];
}
enqueue(value) {
let back = this.queue[this.queue.length - 1];
while (back !== undefined && back < value) {
this.queue.pop();
back = this.queue[this.queue.length - 1];
}
this.queue.push(value);
}
dequeue(value) {
let front = this.front();
if (front === value) {
this.queue.shift();
}
}
front() {
return this.queue[0];
}
}
var maxSlidingWindow = function (nums, k) {
let helperQueue = new MonoQueue();
let i = 0, j = 0;
let resArr = [];
while (j < k) {
helperQueue.enqueue(nums[j++]);
}
resArr.push(helperQueue.front());
while (j < nums.length) {
helperQueue.enqueue(nums[j]);
helperQueue.dequeue(nums[i]);
resArr.push(helperQueue.front());
i++, j++;
}
return resArr;
};
|
时间复杂度：O(n)。
空间复杂度：O(k)。
