带你读《图解算法小抄》十八、队列（1）https://developer.aliyun.com/article/1348049?groupCode=tech_library
2. 滑动窗口的最大值
给定一个整数数组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，用于存储滑动窗口中的元素索引。
- 遍历数组nums，并执行以下操作：
- 在添加新元素之前，先检查队列queue的头部元素是否超出滑动窗口范围。如果超出，则将头部元素移除。
- 然后，比较新元素与队列queue尾部元素所对应的数组元素的大小。如果新元素大于等于尾部元素，则将尾部元素移除，直到队列queue为空或者新元素小于尾部元素。
- 将新元素的索引添加到队列queue的尾部。
- 如果当前窗口已经达到大小k，则将队列queue头部元素所对应的数组元素作为当前窗口的最大值。
- 遍历完整个数组后，我们将得到所有滑动窗口的最大值数组。
2）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 中。
带你读《图解算法小抄》十八、队列（3）https://developer.aliyun.com/article/1348047?groupCode=tech_library
