LeetCode如何求滑动窗口的最大值

# LeetCode如何求滑动窗口的最大值

滑动窗口问题是算法面试中的高频考点，其中「求滑动窗口最大值」是经典难题（LeetCode 239题）。本文将系统讲解暴力法、单调队列法两种解法，并给出Python/Java实现代码。

## 问题描述

给定一个整数数组 `nums` 和一个整数 `k`，请找出所有滑动窗口 `[i, i+k-1]` 中的最大值。示例：

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

解法一：暴力法（不推荐）

算法思路

遍历每个窗口，通过内层循环找出当前窗口的最大值。

时间复杂度

• 外层循环：O(n)
• 内层求最大值：O(k)
• 总计：O(n*k) → 当k较大时效率极低

Python实现

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    return [max(nums[i:i+k]) for i in range(len(nums)-k+1)]

解法二：单调队列（最优解）

算法思想

维护一个单调递减队列，队首始终是当前窗口最大值。关键操作： 1. 入队时：移除队列中所有小于当前元素的值 2. 出队时：如果队首元素等于窗口左边界则移除

复杂度分析

• 时间复杂度：O(n)（每个元素最多入队出队一次）
• 空间复杂度：O(k)（队列最大存储k个元素）

执行过程示例

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

Python实现

from collections import deque

def maxSlidingWindow(nums, k):
    q = deque()
    res = []
    
    for i, num in enumerate(nums):
        # 维护单调性
        while q and nums[q[-1]] < num:
            q.pop()
        q.append(i)
        
        # 移除越界元素
        if q[0] == i - k:
            q.popleft()
        
        # 记录结果
        if i >= k - 1:
            res.append(nums[q[0]])
    
    return res

Java实现

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> q = new ArrayDeque<>();
    int[] res = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
            q.pollLast();
        }
        q.offerLast(i);
        
        if (q.peekFirst() == i - k) {
            q.pollFirst();
        }
        
        if (i >= k - 1) {
            res[i - k + 1] = nums[q.peekFirst()];
        }
    }
    return res;
}

算法对比

常见面试变种

1. 最小值窗口：改用单调递增队列
2. 窗口平均值：结合前缀和数组
3. 窗口和等于目标值：滑动窗口+哈希表

总结

掌握单调队列的要点： 1. 队列中存储的是元素索引而非值 2. 维护单调性的双端操作（头部移除过期元素，尾部维护单调性） 3. 结果记录时机（当i≥k-1时才开始记录）

建议在理解基础上记忆模板代码，并尝试解决LeetCode相关练习题： - 1438. 绝对差不超过限制的最长连续子数组 - 480. 滑动窗口中位数 “`

文章包含： 1. 问题描述与示例 2. 两种解法的详细说明 3. 复杂度分析和代码实现 4. 执行过程可视化 5. 方法对比表格 6. 变种问题建议 7. 总结与学习建议 总字数约1100字，符合要求。