题目

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值

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

思路

使用一个双端队列（队列两面都可进出），用于存储处于窗口中的值的下标，保证窗口头部元素永远是窗口最大值

  1. 当前进入的元素下标 - 窗口头部元素的下标 >= k 队列头部元素移出队列（队列头部元素已经不在窗口内了）
  2. 如果当前数字大于队列尾，则删除队列尾，直到当前数字小于等于队列尾，或者队列空（保证队列左侧永远是最大的值）
  3. 队列元素入队
  4. 第 k 次遍历后开始向结果中添加最大值
  5. 重复 1,2,3,4 步

实现

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
function maxSlidingWindow(nums, k) {
  // window 即是窗口也是双端队列
  const window = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // 如果最左侧的元素在窗口外，弹出队列
    // 这里保证了窗口宽度不大于 k
    if (i - window[0] >= k) {
      window.shift();
    }
    let windowEndIndex = window.length - 1;
    // 如果窗口最右侧的元素小于等于要滑入窗口的元素，弹出最右侧元素
    // 保证了最左侧元素永远是是窗口内的最大值，即从左到右从大到小排序
    while (windowEndIndex >= 0 && nums[window[windowEndIndex]] <= nums[i]) {
      windowEndIndex--;
      window.pop();
    }
    window.push(i);
    // 因为是求窗口内最大值，所以要等窗口完全进入数组才开始计算结果
    if (i >= k - 1) {
      result.push(nums[window[0]]);
    }
  }
  return result;
}