题目描述给你一个整数数组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^41 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 [] i0, nums[0]1: 1 入队从后pop掉比1小的元素无 deque [0] // 存放下标 left 0 3 - 1 2当前窗口还不够3个不记录答案 i1, nums[1]3: 3 入队从后pop掉比3小的1 deque [1] i2, nums[2]-1: -1 入队不pop-1 3 deque [1,2] left 2, deque[0]1 0有效 记录答案: ans[2] nums[1] 3 i3, 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 i4, 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 i5, nums[5]3: 3 入队不pop3 5 deque [4,5] left 5, deque[0]4 5无效pop_front deque [5] 记录答案: ans[5] nums[5] 3 i6, 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 i7, 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 (窗口左边界) 遍历: i0: nums[0]1 deque: [0] left -2 (窗口未形成) i1: nums[1]3 pop: 0 (1 3) deque: [1] left -1 (窗口未形成) i2: nums[2]-1 deque: [1,2] left 0 deque[0]1 0, ans.push(3) i3: nums[3]-3 deque: [1,2,3] left 1 deque[0]1 1, pop_front - [2,3] ans.push(-1) i4: 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) i5: nums[5]3 deque: [4,5] left 3 deque[0]4 3, pop_front - [5] ans.push(3) i6: nums[6]6 pop: 5 (6 3) deque: [4,6] left 4 deque[0]4 4, pop_front - [6] ans.push(6) i7: 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:vectorintmaxSlidingWindow(vectorintnums,intk){intnnums.size();vectorintans(n-k1);dequeintdeque;for(inti0;in;i){// 1. 新元素进来从后往前pop掉所有比它小的while(!deque.empty()nums[deque.back()]nums[i]){deque.pop_back();}deque.push_back(i);// 2. 检查队头是否还在窗口内intlefti-k1;// 窗口左边界if(deque.front()left){deque.pop_front();}// 3. 记录答案窗口形成后才有答案if(ik-1){ans[left]nums[deque.front()];}}returnans;}};四、逐行解析dequeintdeque;双端队列存储数组元素的下标从左到右按递减顺序排列队头永远是当前窗口最大值while(!deque.empty()nums[deque.back()]nums[i]){deque.pop_back();}新元素 nums[i] 比队尾元素大队尾元素不可能成为最大值了被 nums[i] 挡住了从后 pop 掉所有比 nums[i] 小的元素deque.push_back(i);将当前下标加入队尾intlefti-k1;计算当前窗口的左边界窗口是 [i-k1, i]if(deque.front()left){deque.pop_front();}检查队头是否在窗口内如果队头的下标小于左边界说明已经不在窗口内了pop掉if(ik-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 1nums [1, 3, -1], k 1 i0: deque[0], left0, i0, ans[0]nums[0]1 i1: deque[1], left1, i0, ans[1]nums[1]3 i2: deque[2], left2, i0, 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中等单调队列 DP1438绝对差不超过 K 的最长子数组中等单调队列记录最大最小862和至少为 K 的最短子数组困难单调队列 前缀和480滑动窗口中位数困难滑动窗口 有序集合十一、总结要点内容核心思想单调递减队列队头是当前窗口最大值入队操作从后pop掉所有比新元素小的然后入队出队操作检查队头是否在窗口内不在则pop时间复杂度O(n)每元素最多入队出队各一次空间复杂度O(k)队列最多存 k 个元素关键点deque 存下标而非值便于判断过期易错点 vs 的选择滑动窗口最大值是单调队列的经典应用通过维护一个递减的队列实现了 O(n) 时间复杂度的算法。核心思想是把不可能成为最大值的元素从队尾pop掉队头自然就是最大值。
【力扣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^41 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 [] i0, nums[0]1: 1 入队从后pop掉比1小的元素无 deque [0] // 存放下标 left 0 3 - 1 2当前窗口还不够3个不记录答案 i1, nums[1]3: 3 入队从后pop掉比3小的1 deque [1] i2, nums[2]-1: -1 入队不pop-1 3 deque [1,2] left 2, deque[0]1 0有效 记录答案: ans[2] nums[1] 3 i3, 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 i4, 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 i5, nums[5]3: 3 入队不pop3 5 deque [4,5] left 5, deque[0]4 5无效pop_front deque [5] 记录答案: ans[5] nums[5] 3 i6, 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 i7, 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 (窗口左边界) 遍历: i0: nums[0]1 deque: [0] left -2 (窗口未形成) i1: nums[1]3 pop: 0 (1 3) deque: [1] left -1 (窗口未形成) i2: nums[2]-1 deque: [1,2] left 0 deque[0]1 0, ans.push(3) i3: nums[3]-3 deque: [1,2,3] left 1 deque[0]1 1, pop_front - [2,3] ans.push(-1) i4: 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) i5: nums[5]3 deque: [4,5] left 3 deque[0]4 3, pop_front - [5] ans.push(3) i6: nums[6]6 pop: 5 (6 3) deque: [4,6] left 4 deque[0]4 4, pop_front - [6] ans.push(6) i7: 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:vectorintmaxSlidingWindow(vectorintnums,intk){intnnums.size();vectorintans(n-k1);dequeintdeque;for(inti0;in;i){// 1. 新元素进来从后往前pop掉所有比它小的while(!deque.empty()nums[deque.back()]nums[i]){deque.pop_back();}deque.push_back(i);// 2. 检查队头是否还在窗口内intlefti-k1;// 窗口左边界if(deque.front()left){deque.pop_front();}// 3. 记录答案窗口形成后才有答案if(ik-1){ans[left]nums[deque.front()];}}returnans;}};四、逐行解析dequeintdeque;双端队列存储数组元素的下标从左到右按递减顺序排列队头永远是当前窗口最大值while(!deque.empty()nums[deque.back()]nums[i]){deque.pop_back();}新元素 nums[i] 比队尾元素大队尾元素不可能成为最大值了被 nums[i] 挡住了从后 pop 掉所有比 nums[i] 小的元素deque.push_back(i);将当前下标加入队尾intlefti-k1;计算当前窗口的左边界窗口是 [i-k1, i]if(deque.front()left){deque.pop_front();}检查队头是否在窗口内如果队头的下标小于左边界说明已经不在窗口内了pop掉if(ik-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 1nums [1, 3, -1], k 1 i0: deque[0], left0, i0, ans[0]nums[0]1 i1: deque[1], left1, i0, ans[1]nums[1]3 i2: deque[2], left2, i0, 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中等单调队列 DP1438绝对差不超过 K 的最长子数组中等单调队列记录最大最小862和至少为 K 的最短子数组困难单调队列 前缀和480滑动窗口中位数困难滑动窗口 有序集合十一、总结要点内容核心思想单调递减队列队头是当前窗口最大值入队操作从后pop掉所有比新元素小的然后入队出队操作检查队头是否在窗口内不在则pop时间复杂度O(n)每元素最多入队出队各一次空间复杂度O(k)队列最多存 k 个元素关键点deque 存下标而非值便于判断过期易错点 vs 的选择滑动窗口最大值是单调队列的经典应用通过维护一个递减的队列实现了 O(n) 时间复杂度的算法。核心思想是把不可能成为最大值的元素从队尾pop掉队头自然就是最大值。
