239. 滑动窗口最大值

Posted on Edited on In Views: Word count in article: 1.4k Reading time ≈ 1 mins.

239 滑动窗口最大值

题目链接：239. 滑动窗口最大值

核心思考：如何突破性能瓶颈？

在处理“滑动窗口最大值”时，最直观的暴力思路是维护一个窗口的头尾指针，并在每次窗口滑动后，对当前窗口内的子数组执行 max() 操作。

在逻辑上这毫无瑕疵，但在算法效率上却面临严峻瓶颈：

  • 每次移动指针后，都需要在长度为 $k$ 的窗口内遍历寻找最大值。
  • 整体时间复杂度退化为 $O(n \times k)$。
  • 考虑到数据规模 $n$ 通常在 $10^5$ 级别，如果 $k$ 也很大，这种 $10^{10}$ 量级的计算量会导致必定触发 TLE (Time Limit Exceeded)。

因此，优化的核心在于如何将寻找窗口最大值的时间复杂度从 $O(k)$ 降低到 $O(1)$ 或 $O(\log k)$，从而实现整体 $O(n)$ 的时间复杂度。

解题思路：单调队列 (Monotonic Queue)

为了实现 $O(n)$，我们需要引入单调队列。它的核心哲学非常极致：及时剔除那些永远不可能成为最大值的无效状态。

算法核心逻辑

  1. 存储索引而非数值：队列中存储数组 nums 的下标。这样可以根据下标精准判断当前队头元素是否已经“过期”（即滑出了长度为 $k$ 的窗口边界）。
  2. 维护单调递减性：当遍历到新元素 nums[i] 时，如果它大于队列尾部索引对应的元素，说明队尾元素“失去价值”——它不仅比当前元素小，而且比当前元素更早滑出窗口，未来绝无可能成为最大值。此时必须将队尾比它小的元素全部弹出（Pop）。
  3. 清理过期边界：每次滑动，检查队头索引是否已经小于等于 $i - k$。如果是，说明该最大值已失效，需从队头移出（PopLeft）。

经过上述维护，队头元素永远是当前窗口内最大元素的索引。

代码实现

方法一：Go 语言实现 (切片模拟双端队列)

在 Go 中，我们可以利用 Slice 切片操作充当双端队列。通过将初始化逻辑与主循环合并，并利用 i >= k-1 这一条件来控制结果的收集，实现高度紧凑的代码结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
        return nil
    }
    var res, deque []int 

    for i := 0; i < len(nums); i++ {
        // 1. 清理滑出左边界的队头索引
        if len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }
        // 2. 维护单调递减：弹出队尾较小的元素
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
            deque = deque[:len(deque)-1]
        }
        // 3. 入队当前索引
        deque = append(deque, i)
        // 4. 窗口形成后收集结果
        if i >= k-1 {
            res = append(res, nums[deque[0]])
        }
    }
    return res
}

image-compressed.png

方法二：Python 语言实现 (collections.deque)

与 Go 不同，Python 若使用普通 list 执行 pop(0) 会引发 $O(n)$ 的内存拷贝。因此，必须调用内置的 collections.deque 以确保两端增删均为 $O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import collections
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k == 0:
            return []
        
        res = []
        q = collections.deque() # 存储下标
        
        for i in range(len(nums)):
            # 1. 如果队头元素已滑出窗口，弹出
            if q and q[0] <= i - k:
                q.popleft()
            
            # 2. 维护单调递减性质
            while q and nums[q[-1]] <= nums[i]:
                q.pop()
                
            q.append(i)
            
            # 3. 当窗口大小达到 k 时，记录结果
            if i >= k - 1:
                res.append(nums[q[0]])
                
        return res

image.png

复杂度分析

  • 时间复杂度：$O(n)$。虽然代码中嵌套了循环，但每个下标最多被入队一次、出队一次，因此总的操作次数与数组长度 $n$ 成正比。
  • 空间复杂度：$O(k)$。单调队列中最多存储 $k$ 个元素的索引（在元素严格递减的情况下）。

进阶探讨：工程实现中的权衡

在推演过程中，一个值得思考的问题是：是否需要先单独初始化前 $k$ 个元素？

从工程优化的视角来看，这是一个典型的分支预测 (Branch Prediction) 与 DRY (Don’t Repeat Yourself) 原则的权衡：

  1. 单循环版（当前代码）：代码高度复用，结构紧凑。代价是每次迭代都要执行一次 if i >= k-1 的分支判断。
  2. 分离初始化版（双循环）：剥离前 $k$ 个元素的处理，避免在主循环中做无意义的边界检查，对 CPU 的分支预测更友好。代价是维护单调性的内部循环逻辑会被重复书写。

在绝大多数应用层场景中，单循环中简单的 if 判断开销微乎其微。但如果是处在底层内核或高性能计算的热点路径（Hot Path）上，拆分循环以消灭条件分支则是标准的极致优化手段。

这种“在时间轴上前瞻性地剪除劣势状态”的思想，不仅适用于算法题，也与系统资源回收和容器状态管理的优化逻辑高度一致。