leetcode-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

输入：nums = [1], k = 1
输出：[1]

---

解题思路：
Alice: 你咋想起来做这道了 ？
Bob: 我其实是在做另一道题目，多重背包的优化之单调队列优化，但是我不知道什么是单调队列，所以我需要先做一下这道题，学习一些单调队列。
Alice: 所有，有什么思路吗 ？
Bob: 学习的话，想个十分钟吧，然后看题解得了。

Alice: 好吧，题解看明白了吗 ？
Bob: 有点迷，我还是先上手写一下吧。
Alice: 没通过吧，有几个概念你要先了解。队列知道吧，先进先出。双端队列知道吗？两边都能进，两边都能出。你老用 JavaScript 的话，应该知道数组的 push pop shift unshift 这些方法吧，这就是双端队列。
Bob: 然后呢 ？
Alice：你还得知道单调队列，还有这题为啥需要单调队列来解。单调队列就是，队列中的值是单调的，单调就是数学上的那个单调，单调递增或者单调递减或者单调不增或者单调不减。
Bob: 那为啥要用单调队列呢 ？
Alice: 还是得读题啊。这题不是让求解滑动窗口的最大值吗 ？然后数组长度最大 10^5，k 的取值最大也是 10^5，按照最大的计算量 k取最大长度的一半也就是 5*10^4 然后每次都求最大值，计算量也就是 10^5 * (5 * 10^4)^2也就是 2.5 * 10^14, 时间限制是 1s 的话，一定会超时的。
Bob: 所以我们需要单调队列 ？
Alice: 差不多，单调队列非常适合这道题，这道题是让求 k 时间窗口的最大值，单调队列的头或尾一定是最大值。我们只需要在窗口滑动的过程中不断地维护队列就可以了。
Bob: 怎么维护呢 ？
Alice: 这里有两个点需要注意。1是要在维护队列的过程中不断干掉超出 k 时间窗口的值，2是要及时干掉那些不需要的值，比如说 nums[i] > nums[i-1] 的时候，nums[i-1] 就没必要继续留在队列中了，要求的是最大值 nums[i] 比 nums[i-1] 更大且更 ”年轻“ ，求最大值的时候 nums[i] 一定会覆盖 nums[i-1]。当然这里不止 i-1 前面 ”更老更小“ 的都应该干掉。
Bob: 所以我们的数据结构中还应该有下标，通过下标来计算某个值是否超出 k 时间窗口 ？
Alice: 对的，而另一个维护队列的时机就是在新元素入队之前，或者入队的时候。
Bob: 还有什么要注意的吗 ？
Alice: 有的，有两个点，一是初始化的时候也要维护单调队列，还有就是每次维护其实是在队首和队尾都要维护，队尾要干掉那些不必要的，队首要保证在 k 时间窗口内最大。
Bob: k 时间窗口最大我是这样理解的，队尾的维护会把比较小的干掉，这样队首元素出去之后，从队尾补上来的，应该总是剩下的最大的。
Alice: 对的。
Bob: 还是挺有技巧的，上代码吧。

---

代码：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {

  const ans = []
  // 初始化 queue
  const queue = [];
  for(let i=0; i<k; ++i) {
    // 维护队尾，去除不必要的又老又小的值
    while (queue.length > 0 && queue[queue.length-1][0] <= nums[i]) {
      queue.pop();
    }
    // 新大值入队
    queue.push([nums[i], i]);
  }

  ans.push(queue[0][0]);

  for (let i=k; i<nums.length; ++i) {
    // 维护队尾，去除不必要的又老又小的值
    while (queue.length > 0 && queue[queue.length-1][0] <= nums[i]) {
      queue.pop();
    }
    // 新大值入队
    queue.push([nums[i], i]);
    // 维护队首
    while (queue.length > 0 && queue[0][1] + k <= i) {
      queue.shift();
    }

    ans.push(queue[0][0]);
  }

  return ans;
};
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

测试用例：

[9,10,9,-7,-4,-8,2,-6]
5
[10,10,9,2]
1
2
3

参考：

• 题目链接
• 相关题目-多重背包的单调队列优化