双指针专题(九)：谁是窗口里的老大？——「滑动窗口最大值」

这道题是LC 239. 滑动窗口最大值(Hard)。 它是所有涉及“区间最值”问题的鼻祖。面试官考这道题，看的就是你能不能在 O(N) 的时间里解决问题，而不是傻傻地用 O(N×K) 去遍历。

场景想象：有一个固定长度为k的窗口在数组上滑动。这就好比一个**“淘汰制的晋升通道”**。

• 规则 1（能力说话）：如果你比前面的老员工（队列里的元素）能力强（数值大），那前面的老员工就废了，永远不可能成为这个窗口里的老大（最大值），直接把他们踢走。

• 规则 2（任期限制）：你是这一届最强的（队头），但如果你的任期到了（滑出了窗口范围），你也得退休。

力扣 239. 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/

题目分析：

• 输入：整数数组nums，窗口大小k。

• 输出：数组，包含每次滑动后的最大值。

例子：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

1. [1, 3, -1]-> Max: 3

2. [3, -1, -3]-> Max: 3

3. [-1, -3, 5]-> Max: 5

4. ...

核心思维：单调队列 (Monotonic Queue)

我们需要维护一个双端队列 (Deque)。 为了保证队头永远是最大值，这个队列里的元素必须严格单调递减（从大到小）。

队列里存什么？存下标 (index)！而不是存数值。

• 为什么？因为我们需要通过下标来判断队头元素是否已经**“过期”**（滑出窗口）。如果只存数值，就不知道它什么时候该退休了。

操作三部曲：

1. 入队（去尾）：新元素nums[i]来了。

   • 如果队尾元素 < 新元素：说明队尾是个“又老又弱”的废棋，直接pop踢掉。

   • 重复这个过程，直到队尾元素 >= 新元素，或者队列空了。

   • 把nums[i]的下标放入队尾。

   • (这一步保证了队列是单调递减的)

2. 出队（去头）：

   • 检查队头下标是否已经小于i - k + 1（即是否滑出了当前窗口）。

   • 如果是，shift踢掉队头。

3. 记录结果：

   • 只要窗口形成（i >= k - 1），队头元素对应的数值就是当前窗口的最大值。

代码实现 (JavaScript)

JavaScript

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { // 队列存放的是下标 index const queue = []; const result = []; for (let i = 0; i < nums.length; i++) { // 1. 【入队前的清理】：维护单调递减 // 只要队尾元素比当前元素小，就把它踢走 // 因为当前元素更强，而且更晚离开窗口，所以队尾那些“弱者”永远没机会出头了 while (queue.length > 0 && nums[queue[queue.length - 1]] < nums[i]) { queue.pop(); } // 新元素入队 (存下标) queue.push(i); // 2. 【检查队头合法性】：老大多久退休？ // 计算窗口左边界：i - k + 1 // 如果队头下标 < i - k + 1，说明它已经滑出去了 if (queue[0] <= i - k) { queue.shift(); // 移除队头 } // 3. 【记录结果】 // 只有当窗口完全形成后（也就是 i 走到 k-1 时），才开始记录 if (i >= k - 1) { // 队头永远是当前窗口的最大值 result.push(nums[queue[0]]); } } return result; };

深度模拟

nums = [1, 3, -1, -3, 5],k = 3

1. i=0 (值1): 队列[0](对应值1)。

2. i=1 (值3):

   • 3 比 1 大 -> 弹出 0。

   • 入队 1。队列[1](对应值3)。

3. i=2 (值-1):

   • -1 比 3 小 -> 保持单调性。

   • 入队 2。队列[1, 2](对应值 3, -1)。

   • 窗口成型：记录最大值nums[1] = 3。Res=[3]

4. i=3 (值-3):

   • -3 比 -1 小 -> 入队 3。队列[1, 2, 3](对应值 3, -1, -3)。

   • 检查队头：队头是 1。当前窗口范围[1, 3]。队头还在，不用退休。

   • 记录最大值nums[1] = 3。Res=[3, 3]

5. i=4 (值5):

   • 5 比 -3 大 -> 弹 3。

   • 5 比 -1 大 -> 弹 2。

   • 5 比 3 大 -> 弹 1。

   • 入队 4。队列[4](对应值 5)。

   • 记录最大值nums[4] = 5。Res=[3, 3, 5]

总结

这道题是单调队列的入门即巅峰。 请记住这个“职场法则”：一旦新来的比你强，你就被淘汰了（pop）；即使你是最强的，时间到了也得走人（shift）。

下一题预告：K 个不同整数的子数组

这一题（LC 239）解决的是“窗口内的最值”。 下一题LC 992. K 个不同整数的子数组（专项十），我们要解决的是一个极具数学技巧的计数问题。

• 题目：求有多少个子数组，恰好包含K种不同的整数。

• 难点：直接求“恰好 K”很难。我们需要把问题转化为“最多 K” - “最多 K-1”。这是一个非常高级的滑动窗口思想。

准备好迎接双指针专题的大结局了吗？