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 为例：

步骤	操作	队列状态	当前窗口最大值
1	处理1	[1]	-
2	处理3	[3]	-
3	处理-1	[3, -1]	3
4	移除1	[3, -1]	3
5	处理-3	[3, -1,-3]	3
6	移除3	[-1,-3]	-1
7	处理5	[5]	5

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; } 

算法对比

方法	时间复杂度	空间复杂度	适用场景
暴力法	O(n*k)	O(1)	仅适用于k极小情况
单调队列法	O(n)	O(k)	通用最优解

常见面试变种

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

总结

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

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

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