【力扣100题】62.滑动窗口最大值
题目描述
给你一个整数数组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： 输入：nums = [1], k = 1 输出：[1]提示：
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
解题思路总览
| 方法 | 核心思想 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|
| 单调递减队列 | 维护一个递减的双端队列 | O(n) | O(k) | 推荐解法 |
| 暴力法 | 每次遍历窗口找最大值 | O(n*k) | O(1) | 会超时 |
| 堆/优先队列 | 用大顶堆存储窗口元素 | O(n log k) | O(k) | 不够优 |
| 分块 + 预处理 | RMQ/稀疏表 | O(n) | O(n) | 预处理复杂 |
一、核心解法：单调递减队列（双端队列）
核心思想
使用一个双端队列，维护窗口内的元素，保证队列从左到右是递减的。
- 队列中存储数组元素的下标
- 队列头是当前窗口的最大值
- 新元素进来时，把比它小的都pop掉（因为它们不可能成为最大值）
nums = [1,3,-1,-3,5,3,6,7], k = 3 滑动窗口过程： 窗口 [1,3,-1]： 3 入队，把比 3 小的 1 pop 掉 队列: [3, -1]（存放下标：[1,2]） 最大值: nums[1] = 3 窗口 [3,-1,-3]： -1 入队，不影响（比 3 小） -3 入队，不影响 队列: [3, -1, -3]（存放下标：[1,2,3]） 最大值: nums[1] = 3 窗口 [-1,-3,5]： 5 入队，把比 5 小的 -1, -3 pop 掉 队列: [5]（存放下标：[4]） 最大值: nums[4] = 5 注意：3 已经不在窗口内了（因为 3 的下标是 1，窗口左边界是 2）关键洞察
单调递减队列的核心： 1. 新元素进来时，从后往前pop掉所有比它小的元素 - 因为那些元素永远不可能成为最大值（被新元素挡住了） 2. 检查队头是否还在窗口内 - 如果队头的下标 < left，说明它已经不在窗口内了，需要pop掉 3. 队头永远是当前窗口的最大值图解
nums = [1,3,-1,-3,5,3,6,7], k = 3 初始状态: deque = [] i=0, nums[0]=1: 1 入队，从后pop掉比1小的元素（无） deque = [0] // 存放下标 left = 0 + 3 - 1 = 2，当前窗口还不够3个，不记录答案 i=1, nums[1]=3: 3 入队，从后pop掉比3小的：1 deque = [1] i=2, nums[2]=-1: -1 入队，不pop（-1 < 3） deque = [1,2] left = 2, deque[0]=1 >= 0，有效 记录答案: ans[2] = nums[1] = 3 i=3, nums[3]=-3: -3 入队，不pop deque = [1,2,3] left = 3, deque[0]=1 < 3，无效，pop_front deque = [2,3] 记录答案: ans[3] = nums[2] = -1 i=4, nums[4]=5: 5 入队，从后pop掉比5小的：-1, -3 deque = [1,4] left = 4, deque[0]=1 < 4，无效，pop_front deque = [4] 记录答案: ans[4] = nums[4] = 5 i=5, nums[5]=3: 3 入队，不pop（3 < 5） deque = [4,5] left = 5, deque[0]=4 < 5，无效，pop_front deque = [5] 记录答案: ans[5] = nums[5] = 3 i=6, nums[6]=6: 6 入队，从后pop掉比6小的：3 deque = [4,6] left = 6, deque[0]=4 < 6，无效，pop_front deque = [6] 记录答案: ans[6] = nums[6] = 6 i=7, nums[7]=7: 7 入队，从后pop掉比7小的：6 deque = [4,7] left = 7, deque[0]=4 < 7，无效，pop_front deque = [7] 记录答案: ans[7] = nums[7] = 7 结果: [3,3,5,5,6,7]二、算法流程图
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3 初始化: deque = [] ans = [] left = i - k + 1 (窗口左边界) 遍历: i=0: nums[0]=1 deque: [0] left = -2 (窗口未形成) i=1: nums[1]=3 pop: 0 (1 < 3) deque: [1] left = -1 (窗口未形成) i=2: nums[2]=-1 deque: [1,2] left = 0 deque[0]=1 >= 0, ans.push(3) i=3: nums[3]=-3 deque: [1,2,3] left = 1 deque[0]=1 < 1, pop_front -> [2,3] ans.push(-1) i=4: nums[4]=5 pop: 2,3 (5 > -1, 5 > -3) deque: [1,4] left = 2 deque[0]=1 < 2, pop_front -> [4] ans.push(5) i=5: nums[5]=3 deque: [4,5] left = 3 deque[0]=4 < 3, pop_front -> [5] ans.push(3) i=6: nums[6]=6 pop: 5 (6 > 3) deque: [4,6] left = 4 deque[0]=4 < 4, pop_front -> [6] ans.push(6) i=7: nums[7]=7 pop: 6 (7 > 6) deque: [4,7] left = 5 deque[0]=4 < 5, pop_front -> [7] ans.push(7) 输出: [3,3,5,5,6,7]三、完整代码实现
classSolution{public:vector<int>maxSlidingWindow(vector<int>&nums,intk){intn=nums.size();vector<int>ans(n-k+1);deque<int>deque;for(inti=0;i<n;i++){// 1. 新元素进来，从后往前pop掉所有比它小的while(!deque.empty()&&nums[deque.back()]<=nums[i]){deque.pop_back();}deque.push_back(i);// 2. 检查队头是否还在窗口内intleft=i-k+1;// 窗口左边界if(deque.front()<left){deque.pop_front();}// 3. 记录答案（窗口形成后才有答案）if(i>=k-1){ans[left]=nums[deque.front()];}}returnans;}};四、逐行解析
deque<int>deque;- 双端队列，存储数组元素的下标
- 从左到右按递减顺序排列
- 队头永远是当前窗口最大值
while(!deque.empty()&&nums[deque.back()]<=nums[i]){deque.pop_back();}- 新元素 nums[i] 比队尾元素大
- 队尾元素不可能成为最大值了（被 nums[i] 挡住了）
- 从后 pop 掉所有比 nums[i] 小的元素
deque.push_back(i);- 将当前下标加入队尾
intleft=i-k+1;- 计算当前窗口的左边界
- 窗口是 [i-k+1, i]
if(deque.front()<left){deque.pop_front();}- 检查队头是否在窗口内
- 如果队头的下标小于左边界，说明已经不在窗口内了，pop掉
if(i>=k-1){ans[left]=nums[deque.front()];}- 当 i >= k-1 时，窗口才形成
- 队头就是当前窗口的最大值
五、单调递减队列的原理
为什么从后pop？ 设当前队列: [idx1, idx2, ..., idxm] (对应 nums 值递减) 新元素 nums[i] 入队： 如果 nums[i] > nums[idxm]： idxm 不可能成为最大值了（nums[i] 比它大，且 nums[i] 更晚被移出） pop idxm 继续检查 idxm-1，直到队列为空或 nums[i] <= nums[idx] 为什么从后pop而不是从前往后？ 因为我们要维护递减顺序： - 队头是最大值 - 队尾是最近加入的 从后pop是因为： - 最近加入的元素最有可能被新元素"挡住" - 较早加入的元素在窗口内存在时间更长六、与优先队列对比
| 维度 | 单调递减队列 | 优先队列（堆） |
|---|---|---|
| 时间复杂度 | O(n) | O(n log k) |
| 空间复杂度 | O(k) | O(k) |
| 维护方式 | 队列单调性 | 堆的有序性 |
| 过期元素处理 | 需要检查并pop | 需要标记并跳过 |
| 特点 | 每元素最多入队出队各一次 | 每元素入堆出堆各一次 |
七、复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 单调递减队列 | O(n) | O(k) | 推荐 |
| 优先队列 | O(n log k) | O(k) | 不够优 |
| 暴力法 | O(n*k) | O(1) | 会超时 |
| 分块预处理 | O(n) | O(n) | 预处理复杂 |
详细分析：
时间复杂度： 每个元素最多入队一次、出队一次 总计：O(2n) = O(n) 空间复杂度： 双端队列最多存 k 个元素（下标） O(k)八、边界情况分析
| 情况 | 处理方式 |
|---|---|
| k = 1 | 每个窗口只有一个元素，答案就是数组本身 |
| k = n | 只有一个窗口，答案是整个数组的最大值 |
| 有重复元素 | 从后pop时用 <= 而不是 <，保证只pop掉比新元素小的 |
| 全是负数 | 正常处理，队头永远是窗口最小值（相对最大） |
示例：k = 1
nums = [1, 3, -1], k = 1 i=0: deque=[0], left=0, i>=0, ans[0]=nums[0]=1 i=1: deque=[1], left=1, i>=0, ans[1]=nums[1]=3 i=2: deque=[2], left=2, i>=0, ans[2]=nums[2]=-1 输出: [1, 3, -1]九、面试追问 FAQ
| 问题 | 回答要点 |
|---|---|
| Q: 为什么用双端队列而不是单端队列？ | 需要从队头取最大值，也需要从队尾入新元素、pop小元素，两端都要操作 |
| Q: 为什么从后pop而不是从前往后？ | 从后pop可以维护递减顺序，且不影响队头的最大值 |
| Q: 如何处理窗口过期元素？ | 检查队头下标是否小于窗口左边界，小于则pop掉 |
| Q: 为什么条件是 <= 而不是 <？ | 等于时也要pop，因为新元素在后面，旧的先过期 |
| Q: 时间复杂度为什么是 O(n)？ | 每个元素最多入队一次、出队一次，总操作 2n 次 |
| Q: 能否用其他数据结构？ | 可以用堆，但时间复杂度 O(n log k)，不够优 |
十、相关题目
| 题目编号 | 题目名称 | 难度 | 核心差异 |
|---|---|---|---|
| 239 | 滑动窗口最大值 | 困难 | 基础题，单调队列 |
| 剑指 Offer 59 | 滑动窗口的最大值 | 困难 | 同本题 |
| 1696 | 跳跃游戏 VI | 中等 | 单调队列 + DP |
| 1438 | 绝对差不超过 K 的最长子数组 | 中等 | 单调队列记录最大最小 |
| 862 | 和至少为 K 的最短子数组 | 困难 | 单调队列 + 前缀和 |
| 480 | 滑动窗口中位数 | 困难 | 滑动窗口 + 有序集合 |
十一、总结
| 要点 | 内容 |
|---|---|
| 核心思想 | 单调递减队列，队头是当前窗口最大值 |
| 入队操作 | 从后pop掉所有比新元素小的，然后入队 |
| 出队操作 | 检查队头是否在窗口内，不在则pop |
| 时间复杂度 | O(n)（每元素最多入队出队各一次） |
| 空间复杂度 | O(k)（队列最多存 k 个元素） |
| 关键点 | deque 存下标而非值，便于判断过期 |
| 易错点 | <= vs < 的选择 |
滑动窗口最大值是单调队列的经典应用，通过维护一个递减的队列，实现了 O(n) 时间复杂度的算法。核心思想是：把不可能成为最大值的元素从队尾pop掉，队头自然就是最大值。