LeetCode 239 - 滑动窗口最大值（Sliding Window Maximum）

问题描述

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

返回滑动窗口中的最大值。

示例 1：

输入：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

示例 2：

1 2	输入：nums = [1], k = 1 输出：[1]

约束条件：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

解题思路

核心算法：单调队列

这道题的核心思想是使用单调递减队列来维护滑动窗口中的最大值。单调队列的特点是队列中的元素按照从大到小的顺序排列，队首元素始终是当前窗口的最大值。

算法步骤

初始化单调队列：创建一个双端队列来存储数组索引
维护单调性：每次添加新元素时，从队尾移除所有小于等于当前元素的值
处理窗口滑动：当窗口左边界移动时，移除队列中已经不在窗口内的元素
获取最大值：队首元素始终是当前窗口的最大值

关键洞见

单调队列的优势：不需要遍历整个窗口来找到最大值，时间复杂度从 O(k) 降低到 O(1)
索引存储：存储索引而不是值，便于判断元素是否还在窗口内
延迟删除：只有当队首元素确实不在窗口内时才删除，避免频繁操作

实现细节

执行过程示例

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

步骤	当前元素	队列状态	窗口	最大值
1	1	[0]	[1]	-
2	3	[1]	[1,3]	-
3	-1	[1,2]	[1,3,-1]	3
4	-3	[1,2,3]	[3,-1,-3]	3
5	5	[4]	[-1,-3,5]	5
6	3	[4,5]	[-3,5,3]	5
7	6	[6]	[5,3,6]	6
8	7	[7]	[3,6,7]	7

代码实现

func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    if n == 0 || k == 0 {
        return []int{}
    }
    
    // 结果数组
    result := make([]int, 0, n-k+1)
    // 单调递减队列，存储索引
    queue := make([]int, 0)
    
    for i := 0; i < n; i++ {
        // 移除队列中已经不在窗口内的元素
        for len(queue) > 0 && queue[0] <= i-k {
            queue = queue[1:]
        }
        
        // 维护单调递减性质：移除所有小于等于当前元素的值
        for len(queue) > 0 && nums[queue[len(queue)-1]] <= nums[i] {
            queue = queue[:len(queue)-1]
        }
        
        // 将当前元素索引加入队列
        queue = append(queue, i)
        
        // 当窗口大小达到k时，开始记录结果
        if i >= k-1 {
            result = append(result, nums[queue[0]])
        }
    }
    
    return result
}

代码优化版本

func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    result := make([]int, 0, n-k+1)
    queue := make([]int, 0)
    
    for i := 0; i < n; i++ {
        // 移除过期元素
        for len(queue) > 0 && queue[0] <= i-k {
            queue = queue[1:]
        }
        
        // 维护单调递减队列
        for len(queue) > 0 && nums[queue[len(queue)-1]] < nums[i] {
            queue = queue[:len(queue)-1]
        }
        
        queue = append(queue, i)
        
        if i >= k-1 {
            result = append(result, nums[queue[0]])
        }
    }
    
    return result
}

方法比较

方面	暴力解法	单调队列解法
时间复杂度	O(nk)	O(n)
空间复杂度	O(1)	O(k)
优点	实现简单，容易理解	高效，适合大数据量
缺点	时间复杂度过高	实现相对复杂
推荐度	★★☆☆☆	★★★★★

复杂度分析

时间复杂度：O(n)

每个元素最多入队一次：每个索引最多被加入队列一次
每个元素最多出队一次：每个索引最多被移除队列一次
总操作次数：每个元素最多进行 2 次队列操作
结论：时间复杂度为 O(n)

空间复杂度：O(k)

队列大小：最坏情况下队列中存储 k 个元素
结果数组：需要存储 n-k+1 个结果
总空间：O(k) + O(n-k+1) = O(n)
优化后：只考虑队列空间，为 O(k)

关键收获

算法技巧

单调队列的应用场景：
- 滑动窗口最大值/最小值
- 区间最值查询
- 单调栈的变种应用
索引存储的优势：
- 便于判断元素是否在窗口内
- 避免重复计算
- 提高代码可读性
延迟删除策略：
- 减少不必要的队列操作
- 提高算法效率
- 简化实现逻辑

常见陷阱

边界条件处理：
- 数组为空或 k 为 0 的情况
- 窗口大小等于数组长度的情况
队列操作顺序：
- 先移除过期元素，再维护单调性
- 避免在错误时机删除元素
结果记录时机：
- 只有当窗口大小达到 k 时才记录结果
- 注意索引的边界条件

Adrian Wang's blog