单调队列+滑动窗口-洪萨配资

对应力扣239滑动窗口的最大值

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

暴力解法：

设置左右指针形成固定长度 k的窗口（左指针left，右指针right=left+k-1）；
遍历窗口内[left, right]的 k 个元素，找到并记录最大值；
左右指针同时右移 1 位，重复步骤 2，直到窗口滑出数组末尾；
最终将所有窗口的最大值组成数组返回。

时间复杂度为O（n×k）n为数组长度，k为窗口长度

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { const res = []; const n = nums.length; let left = 0; // 右指针最大为n-1，窗口左边界最大为n-k while (left <= n - k) { let right = left + k - 1; let max = nums[left]; // 遍历当前窗口，找最大值（你的核心思路） for (let i = left; i <= right; i++) { max = Math.max(max, nums[i]); } res.push(max); left++; // 指针右移，窗口滑动 } return res; };

为什么暴力法效率低？（重复计算是关键）

暴力法的致命问题是存在大量重复计算：窗口每次只右移 1 位，相邻两个窗口有 k-1 个元素是重叠的，但暴力法会重新遍历全部 k 个元素找最大值，浪费了重叠部分的计算结果

单调队列（双端队列 Deque）

要解决重复计算问题，核心是用一个特殊队列记录「窗口内可能成为最大值的元素下标」，让队列保持单调递减，这样队列队首永远是当前窗口的最大值下标，窗口滑动时只需维护这个队列，无需遍历窗口。

先理解：单调递减队列的核心规则

队列中存储的是nums 的元素下标（而非值），且满足：下标对应的值从队首到队尾严格单调递减（比如队列里的下标对应值是 [5,3,-1]，而非 [3,5,-1]）。

队列的3 个核心维护操作（窗口滑动时执行）：

去尾：当新元素进入窗口时，若新元素值 ≥ 队尾下标对应的值，则队尾出队（因为该队尾元素在窗口内，不可能成为后续任何窗口的最大值，直接淘汰），重复此操作直到队列单调递减；
入队：将新元素的下标加入队尾，此时队列仍保持单调递减；
删头：若队首下标 ≤ 窗口左边界 - 1（说明队首元素已滑出窗口），则队首出队，保证队首始终在窗口内。

最优解核心步骤（全程只需遍历数组 1 次）

初始化双端队列 deque（存储下标）、结果数组 res；
遍历数组 nums 的每个元素，下标为i：
- 步骤 1：去尾→ 维护队列单调递减，淘汰比当前元素小的队尾；
- 步骤 2：入队→ 将i加入 deque 队尾；
- 步骤 3：删头→ 移除滑出窗口的队首下标；
- 步骤 4：记录最大值→ 当i ≥ k-1（说明第一个窗口已形成），将nums[deque[0]]（队首是窗口最大值下标）加入 res；
遍历结束，res 即为所有窗口的最大值数组。

用数组模拟双端队列（shift()删队首、pop()删队尾、push()入队尾）

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { const res = []; const deque = []; // 双端队列，存储nums的下标，保持单调递减 const n = nums.length; for (let i = 0; i < n; i++) { // 操作1：去尾 - 维护单调递减，淘汰比当前元素小的队尾 while (deque.length && nums[i] >= nums[deque[deque.length - 1]]) { deque.pop(); } // 操作2：入队 - 加入当前元素下标 deque.push(i); // 操作3：删头 - 移除滑出窗口的队首（窗口左边界为i-k+1） while (deque[0] <= i - k) { deque.shift(); } // 操作4：记录最大值 - 第一个窗口形成后（i>=k-1），队首即为当前窗口最大值 if (i >= k - 1) { res.push(nums[deque[0]]); } } return res; };