【算法】滑动窗口最大值难度：困难 题目： 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数

难度：困难

题目：

给你一个整数数组 nums，有一个大小为 k

的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值。

示例 1：

输入：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：

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

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

解题思路：

双端队列允许我们在两端进行插入和删除操作，这非常适合用来维护滑动窗口中的元素。在本题中，我们将使用双端队列来存储数组中元素的索引，而非元素本身的值，这样可以方便地维护队列中的元素总是处于递减状态，即队首元素的值总是当前队列中最大的元素。

1. 初始化双端队列：创建一个双端队列 q，用于存储数组中元素的索引。
2. 填充初始窗口：遍历数组的前 k 个元素，将这些元素的索引添加到队列 q 中，同时确保队列中的元素始终是递减的。
3. 滑动窗口：从第 k 个元素开始，每次将新元素的索引加入队列，并且移除队列前端那些不再属于当前窗口的元素的索引。同时，如果队列中前面的元素小于新加入的元素，那么这些前面的元素也需要从队列中移除，因为它们不可能成为接下来窗口中的最大值。
4. 记录最大值：每次窗口滑动后，队列头部的元素索引所对应的数组值即为当前窗口的最大值，将其记录下来。

JavaScript实现：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  let q = []; // 双端队列，存储索引
  let result = [];

  // 填充初始窗口
  for (let i = 0; i < k; i++) {
    while (q.length > 0 && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    q.push(i);
  }

  // 滑动窗口
  for (let i = k; i < nums.length; i++) {
    result.push(nums[q[0]]); // 记录最大值

    // 移除队列中不在窗口内的元素
    while (q.length > 0 && q[0] <= i - k) {
      q.shift();
    }

    // 维护队列递减
    while (q.length > 0 && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }

    q.push(i);
  }

  // 不要忘记最后一个窗口的最大值
  result.push(nums[q[0]]);

  return result;
};