【算法篇】滑动窗口的最大值JavaScript版

滑动窗口的最大值

题目描述：

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度或窗口长度为0的时候，返回空。

• 数据范围： 1≤n≤10000，0≤size≤10000，数组中每个元素的值满足
  ∣val∣≤10000
  要求：空间复杂度 O(n)，时间复杂度 O(n)

• 示例1
  输入：[2,3,4,2,6,2,5,1],3
  返回值：[4,4,6,6,6,5]

• 示例2
  输入：[9,10,9,-7,-3,8,2,-6],5
  返回值：[10,10,9,8]

• 示例3
  输入：[1,2,3,4],5
  返回值：[]

解题思路

方法一：双端队列（Deque）

1. 初始化一个空的双端队列和一个空的结果数组。
2. 遍历数组中的每个元素，对于每个元素：
   • 移除双端队列中不在滑动窗口范围内的元素的索引。
   • 移除双端队列中小于当前元素的元素的索引，因为它们不可能是最大值。
   • 将当前元素的索引添加到双端队列中。
   • 当滑动窗口完全在数组内时，将双端队列首部的元素添加到结果数组中。
3. 返回结果数组。

方法一JavaScript版本代码如下：

function maxSlidingWindow(nums, size) {
  if (size <= 0 || size > nums.length) return [];

  const result = [];
  const deque = []; // 双端队列，用于存储索引

  for (let i = 0; i< nums.length; i++) {
    // 移除不在滑动窗口内的元素的索引
    while (deque.length && deque[0] < i - size + 1) {
      deque.shift();
    }

    // 移除比当前元素小的元素的索引，因为它们不可能是最大值
    while (deque.length && nums[deque[deque.length - 1]]< nums[i]) {
      deque.pop();
    }

    // 将当前元素的索引添加到双端队列中
    deque.push(i);

    // 当滑动窗口完全在数组内时，将当前窗口的最大值添加到结果中
    if (i >= size - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

// 示例
console.log(maxSlidingWindow([2, 3, 4, 2, 6, 2, 5, 1], 3)); // [4, 4, 6, 6, 6, 5]
console.log(maxSlidingWindow([9, 10, 9, -7, -3, 8, 2, -6], 5)); // [10, 10, 9, 8]
console.log(maxSlidingWindow([1, 2, 3, 4], 5)); // []
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

方法二：单调递减栈

1. 初始化一个空的单调递减栈和一个空的结果数组。
2. 遍历数组中的每个元素，对于每个元素：
   • 弹出栈顶元素，直到栈为空或者栈顶元素小于当前元素。
   • 如果弹出的元素索引对应的窗口已经超出范围，则忽略。
   • 如果栈为空或者栈顶元素对应的窗口正好是当前窗口，则将栈顶元素对应的最大值添加到结果数组中。
   • 将当前元素的索引压入栈中。
3. 返回结果数组。

方法二JavaScript版本代码：

function maxSlidingWindow(nums, size) {
  if (size <= 0 || size > nums.length) return [];

  const result = [];
  const stack = []; // 单调递减栈，用于存储索引

  for (let i = 0; i< nums.length; i++) {
    // 弹出栈顶元素，直到栈为空或者栈顶元素对应的值小于当前元素
    while (stack.length && nums[stack[stack.length - 1]]< nums[i]) {
      const index = stack.pop();
      // 如果弹出的索引对应的窗口已经不在范围内，则跳过
      if (i - index + 1 > size) {
        continue;
      }
      // 如果栈为空或者栈顶元素对应的窗口在范围内，则将当前最大值加入结果
      if (stack.length === 0 || i - stack[stack.length - 1] + 1 === size) {
        result.push(nums[index]);
      }
    }
    // 将当前元素的索引压入栈中
    stack.push(i);
  }

  return result;
}

// 示例
console.log(maxSlidingWindow([2, 3, 4, 2, 6, 2, 5, 1], 3)); // [4, 4, 6, 6, 6, 5]
console.log(maxSlidingWindow([9, 10, 9, -7, -3, 8, 2, -6], 5)); // [10, 10, 9, 8]
console.log(maxSlidingWindow([1, 2, 3, 4], 5)); // []
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

总结与类似题解题思路

解决滑动窗口最大值问题的关键在于维护一个能够快速访问当前窗口最大值的机制。这可以通过以下步骤实现：

1. 使用双端队列或单调栈来维护一个有序的序列，使得我们可以快速访问最大值。
2. 在遍历数组的过程中，不断调整这个有序序列，确保它始终反映当前窗口的最大值。
3. 当窗口滑动时，及时移除不再属于窗口的元素，并添加新进入窗口的元素。
4. 在窗口完全在数组内时，记录窗口的最大值。

对于类似的滑动窗口问题，如求最小值、求平均值等，都可以采用类似的思路，关键在于如何维护一个能够快速提供所需信息的辅助数据结构。这种方法的时间复杂度通常是O(n)，因为我们每个元素最多只会被推入和弹出辅助数据结构一次。