LeetCode 239. 滑动窗口最大值

1. 解题思路

题目给出了一个整数数组 nums 和窗口大小 k，要求窗口从左向右移动，并返回每个窗口中的最大值。

最直接的方法是：每次窗口移动后，重新遍历窗口内的 k 个元素，找出其中的最大值。

不过，这样会产生大量重复计算。因为相邻窗口中的元素大部分是相同的，只有一个元素移出、一个新元素加入。

那么，能不能在窗口移动的过程中，直接维护最大值，而不用每次都重新遍历呢？

这里可以使用单调队列。

2. 利用单调队列维护最大值

单调队列的核心思路是：只保留那些还有可能成为当前或后续窗口最大值的元素。

对于这道题，我们希望队列中候选元素的值从队头到队尾严格递减。这样一来，只要队头元素还在窗口内，它就是当前窗口的最大值。

那么，怎样维护这种单调性呢？

假设现在有一个新元素 num 准备加入队列。

我们从队尾开始检查：

  • 如果队尾元素的值小于或等于 num，就将它移除。
  • 不断重复这个过程，直到队列为空，或者队尾元素的值大于 num。
  • 最后将新元素加入队尾。

这里有个值得思考的问题：为什么可以直接删除这些较小的元素？难道不会漏掉后面的答案吗？

其实不会。

因为新元素的位置一定更靠后，这意味着它不仅比被删除的元素更大或相等，而且还会更晚离开滑动窗口。

既然如此，前面那些不大于新元素的候选，就不可能再成为后续窗口的最大值，自然没有必要继续保留。

反过来，如果队尾元素比新元素更大，就不能删除它。因为在它离开窗口之前，仍然有可能是最大值。

例如，依次处理：

纯文本
nums = [1, 3, 2]
  • 加入 1：队列为 [1]。
  • 加入 3：由于 3 >= 1，移除 1，队列变成 [3]。
  • 加入 2：由于 2 < 3，保留 3，再加入 2，队列变成 [3, 2]。

此时队列中的值保持递减，队头的 3 就是最大值。

需要注意，移除队尾元素时必须使用 while，而不是 if。因为一个新元素可能同时淘汰多个旧元素，需要不断检查，直到重新满足单调性。

3. 为什么队列里保存索引？

还有一个问题：窗口会不断向右移动，原来的元素迟早会离开窗口。

即使某个元素很大，只要它已经不在当前窗口内，就不能继续作为最大值。

因此，除了维护单调性，我们还需要判断候选元素是否已经过期。

这里我没有直接保存元素值，而是让队列保存元素在原数组中的索引。

这样既可以通过 nums[dq[0]] 获取队头对应的值，也能根据索引判断它是否还在窗口内。

假设当前遍历到索引 i，窗口大小为 k，那么当前窗口的有效索引范围为：

[i - k + 1, i]

因此，只要队头索引满足：

Python
dq[0] <= i - k

就说明它已经离开当前窗口，需要从队头移除。

经过前面的单调性维护和过期检查后，队列中的索引就同时满足两个条件：

  1. 对应的元素值从队头到队尾严格递减。
  2. 所有候选元素都处于当前窗口的有效范围内。

这样，队头对应的值自然就是当前窗口的最大值。

4. 代码实现

Python 中可以使用 collections 模块提供的 deque，方便从队列两端添加或删除元素。

具体处理顺序如下：

  1. 遍历数组，将当前元素加入窗口。
  2. 从队尾移除所有不大于当前元素的候选，维护单调性。
  3. 将当前元素的索引加入队尾。
  4. 检查队头索引是否已经离开窗口，及时移除过期元素。
  5. 当窗口长度达到 k 后，将队头对应的值加入答案。

Python 代码：

Python
from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq=deque()
        res=[]
        for i,num in enumerate(nums):
            while dq and num>=nums[dq[-1]]:
                dq.pop()
            dq.append(i)
            while dq[0]<=i-k:
                dq.popleft()
            if i>=k-1:
                res.append(nums[dq[0]])
        return res

这里有几个关键操作。

维护队列的单调性：

Python
while dq and num>=nums[dq[-1]]:
    dq.pop()

从队尾不断移除不大于当前元素的候选，确保队列中对应的值保持严格递减。

移除已经过期的元素：

Python
while dq[0]<=i-k:
    dq.popleft()

由于队列中的索引始终按照加入顺序递增，最早过期的元素一定在队头，因此只需要从队头检查和删除。

记录当前窗口的最大值：

Python
if i>=k-1:
    res.append(nums[dq[0]])

当 i >= k - 1 时，说明窗口已经包含了至少 k 个位置，可以开始记录答案。

此时队头索引对应的元素，就是当前窗口的最大值。

5. 复杂度分析

虽然代码中存在两个 while 循环，但时间复杂度并不是 O(n2)O(n^2)。

原因在于：每个元素的索引最多只会入队一次，出队一次。

一个索引可能因为对应的值不够大，被后面的新元素从队尾移除；也可能一直保留到过期，再从队头移除。

但无论是哪种情况，它一旦被移除，就不会再次进入队列。

因此，所有元素的入队和出队操作加起来都是 O(n)O(n)，整个算法的时间复杂度为：

O(n)O(n)

空间方面，单调队列最多保存 k 个窗口内的候选索引，因此辅助空间复杂度为：

O(k)O(k)

此外，结果列表还需要保存 n - k + 1 个窗口最大值。

这道题的关键并不只是使用一个队列，而是通过单调性提前排除那些不可能成为最大值的元素。

这样，每次窗口移动后，只需要维护候选元素并读取队头，就能得到最大值，不必重复遍历整个窗口。

谢谢你读到这里。 ✧