滑动窗口的最大值

给定一个整数数组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

题目分析与解题步骤：

这个问题可以使用队列来解决。我们可以使用一个双端队列来存储滑动窗口中的元素，并保持队列中的元素按照降序排列。

解题步骤如下：

1. 创建一个双端队列queue，用于存储滑动窗口中的元素索引。

2. 遍历数组nums，并执行以下操作：

   • 在添加新元素之前，先检查队列queue的头部元素是否超出滑动窗口范围。如果超出，则将头部元素移除。

   • 然后，比较新元素与队列queue尾部元素所对应的数组元素的大小。如果新元素大于等于尾部元素，则将尾部元素移除，直到队列queue为空或者新元素小于尾部元素。

   • 将新元素的索引添加到队列queue的尾部。

   • 如果当前窗口已经达到大小k，则将队列queue头部元素所对应的数组元素作为当前窗口的最大值。

3. 遍历完整个数组后，我们将得到所有滑动窗口的最大值数组。

JavaScript解题框架：

function maxSlidingWindow(nums, k) {
  const result = [];
  const queue = new Deque();

  for (let i = 0; i < nums.length; i++) {
    // 检查队列头部元素是否超出滑动窗口范围
    if (!queue.isEmpty() && queue.front() <= i - k) {
      queue.pop();
    }

    // 比较新元素与队列尾部元素所对应的数组元素的大小
    while (!queue.isEmpty() && nums[i] >= nums[queue.items[queue.items.length - 1]]) {
      queue.pop();
    }

    // 添加新元素的索引到队列尾部
    queue.push(i);

    // 当窗口达到大小 k 时，将队列头部元素所对应的数组元素作为当前窗口的最大值
    if (i >= k - 1) {
      result.push(nums[queue.front()]);
    }
  }

  return result;
}

在这个框架中，我们使用一个双端队列 Deque 来实现滑动窗口最大值的计算。双端队列中存储的是数组元素的索引，而不是元素本身。

通过遍历数组 nums，我们依次将每个元素加入队列，并维护队列中的元素按照降序排列的规则。

在每次遍历过程中，我们检查队列头部元素是否超出滑动窗口范围，并将超出范围的元素移除。然后，我们比较新元素与队列尾部元素所对应的数组元素的大小，并移除比新元素小的尾部元素，以保持队列的降序特性。

当窗口大小达到 k 时，我们将队列头部元素所对应的数组元素作为当前窗口的最大值，并将其添加到结果数组 result 中。