跟着灵茶山艾府大佬学习算法思路的day17（并没有在一个月内掌握hot100）
b站链接如下：
滑动窗口最大值 题目描述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
输入：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
示例 2：
1
2
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
思路：
很明显能想到暴力的时间复杂度是o(n*2)。优化方法可以这么考虑：想象一下自己在飞机上，自机窗往下看，看到了一座座由数组元素组成的山，数字就是山的高度，随着飞机从左往右飞，视野内的最高山峰是会发生变化的。
在看到4之后，先于4出现的2和1永远不能成为视野里最高的山了。紧接下来又看到一个2，这个2虽然小于4，但有可能是后续的最大值，于是先将2记录下来。当3出现时，2永远不可能成为最大值了，那么就可以去掉2记录3。
在记录最后一个数时，4已经不在视野中，所以可以先把4去掉，再记录2。
我们每次遇到一个数，都会把前面比它小的数去掉，遇到相同数字时也可以去掉，保留最右的数即可。最后我们记录的数从左到右是严格递减的，又因为我们需要在队头和队尾同时操作，所以是单调队列。
判断一道题用单调栈还是单调队列，看有没有窗口：
| 特征 | 用哪个 |
|---|---|
| 固定大小的滑动窗口 + 求窗口内最值 | 单调队列 |
| 找某个方向最近的大/小元素 | 单调栈 |
有窗口用队列，没窗口用栈。单调队列需求的是过期清理，窗口滑动后，队首就需要被删除。如果没有窗口，就没有过期元素，此时队列和栈没有区别，用栈会更简单。
以维护单调性的角度而言，单调栈和单调队列是一致的，单调栈通过弹出栈顶维护单调性，单调队列也通过弹出队尾维护单调性，不过除此之外，单调队列也要通过删除队首维护窗口大小。
代码：
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
var maxSlidingWindow = function(nums, k) {
const ans = [];
const q = new Deque(); // datastructures-js/deque
for (let i = 0; i < nums.length; i++) {
// 1. 右边入
while (!q.isEmpty() && nums[q.back()] <= nums[i]) {
q.popBack(); // 维护 q 的单调性
}
q.pushBack(i); // 注意保存的是下标，这样下面可以判断队首是否离开窗口
// 2. 左边出
const left = i - k + 1; // 窗口左端点
if (q.front() < left) { // 每次循环时都保证队首离开窗口
q.popFront();
}
// 3. 在窗口左端点处记录答案
if (left >= 0) {
// 由于队首到队尾单调递减，所以窗口最大值就在队首
ans.push(nums[q.front()]);
}
}
return ans;
};
总结：
复杂度分析类似单调栈，每个元素出入队至多一次。时间复杂度为o(n)，空间复杂度为o(min(k, U))。
