【LeetCode Hot 100】滑动窗口最大值——多种解法深度解析

题目描述题目链接LeetCode 239. 滑动窗口最大值给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回每个滑动窗口中的最大值。示例text输入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解法一暴力法最直观但超时思路最直接的想法遍历每个窗口在每个窗口中找最大值。代码实现javapublic int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; if (n 0 || k 0) return new int[0]; int[] result new int[n - k 1]; for (int i 0; i n - k; i) { int max nums[i]; for (int j i 1; j i k; j) { max Math.max(max, nums[j]); } result[i] max; } return result; }复杂度分析时间复杂度O(n×k)每个窗口都要遍历k个元素空间复杂度O(1)除结果数组外不需要额外空间优缺点✅ 思路简单易于理解❌ 当k接近n时时间复杂度接近O(n²)在LeetCode上会超时解法二优先队列最大堆思路使用最大堆PriorityQueue来维护窗口内的元素。堆顶始终是最大值。窗口滑动时添加新元素移除离开窗口的元素。代码实现javapublic int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; if (n 0 || k 0) return new int[0]; int[] result new int[n - k 1]; // 最大堆存储数组元素 PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a); // 初始化第一个窗口 for (int i 0; i k; i) { maxHeap.offer(nums[i]); } result[0] maxHeap.peek(); // 滑动窗口 for (int i k; i n; i) { // 移除离开窗口的元素注意这里只能移除一个如果有重复值会出问题 maxHeap.remove(nums[i - k]); // 添加新元素 maxHeap.offer(nums[i]); // 记录当前窗口最大值 result[i - k 1] maxHeap.peek(); } return result; }复杂度分析时间复杂度O(n log k)每次添加/删除操作都是O(log k)空间复杂度O(k)堆的大小为k优缺点✅ 实现相对简单❌remove()操作是O(k)的实际复杂度更高❌ 无法处理重复元素会误删优化版本存储索引javapublic int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] result new int[n - k 1]; // 存储索引的最大堆 PriorityQueueInteger maxHeap new PriorityQueue((a, b) - nums[b] - nums[a]); for (int i 0; i n; i) { // 移除不在窗口内的索引 while (!maxHeap.isEmpty() maxHeap.peek() i - k) { maxHeap.poll(); } maxHeap.offer(i); if (i k - 1) { result[i - k 1] nums[maxHeap.peek()]; } } return result; }解法三双端队列单调队列⭐ 最优解核心思想维护一个单调递减的双端队列队首始终是当前窗口的最大值。关键点队列中存储数组索引而不是值方便判断是否离开窗口保持队列单调递减新元素从队尾进入移除所有比它小的元素移除离开窗口的元素如果队首索引 i - k说明已不在窗口内图解过程以nums [1,3,-1,-3,5,3,6,7], k 3为例texti0: 队列空 → 加入0 → [0] i1: nums[1]3, 比队尾的1大 → 移除0 → 加入1 → [1] i2: nums[2]-1, 比队尾的3小 → 加入2 → [1,2] 窗口形成result[0]nums[1]3 i3: 加入-3 → [1,2,3], 队首1仍在窗口内 → result[1]3 i4: 加入5 → 移除3,2,1 → [4] → result[2]5 i5: 加入3 → [4,5] → result[3]5 i6: 加入6 → 移除5,4 → [6] → result[4]6 i7: 加入7 → 移除6 → [7] → result[5]7代码实现javapublic int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); // 存储索引 for (int i 0; i n; i) { // 1. 移除队列中所有小于当前元素的值维护单调递减 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 2. 将当前元素索引加入队尾 deque.offerLast(i); // 3. 如果队首元素已离开窗口移除它 if (deque.peekFirst() i - k) { deque.pollFirst(); } // 4. 当窗口形成后记录最大值 if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; }为什么用而不是javawhile (!deque.isEmpty() nums[deque.peekLast()] nums[i])使用可以保证队列严格递减不会保留相等值的旧元素。因为新来的相等元素会取代旧元素的位置这样队列中最多只有一个重复值避免窗口滑动时误删问题。复杂度分析时间复杂度O(n)每个元素最多入队和出队一次空间复杂度O(k)队列最多存储k个元素优缺点✅ 时间复杂度最优O(n)✅ 代码简洁优雅✅ 每个元素只处理一次⚠️ 需要理解单调队列的思想解法四动态规划分块法思路将数组分成大小为k的块预处理每个块的前缀最大值和后缀最大值然后每个窗口的最大值就是左右两部分的最大值的较大者。代码实现javapublic int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; if (n 0 || k 0) return new int[0]; int[] leftMax new int[n]; int[] rightMax new int[n]; // 计算从左到右每个块的前缀最大值 for (int i 0; i n; i) { if (i % k 0) { leftMax[i] nums[i]; } else { leftMax[i] Math.max(leftMax[i - 1], nums[i]); } } // 计算从右到左每个块的后缀最大值 for (int i n - 1; i 0; i--) { if (i n - 1 || (i 1) % k 0) { rightMax[i] nums[i]; } else { rightMax[i] Math.max(rightMax[i 1], nums[i]); } } // 每个窗口的最大值 max(窗口右部分的前缀最大, 窗口左部分的后缀最大) int[] result new int[n - k 1]; for (int i 0; i n - k; i) { result[i] Math.max(rightMax[i], leftMax[i k - 1]); } return result; }复杂度分析时间复杂度O(n)空间复杂度O(n)优缺点✅ 时间复杂度也是O(n)✅ 思路巧妙利用分块思想❌ 需要额外的O(n)空间❌ 理解起来比单调队列复杂解法对比总结解法时间复杂度空间复杂度优点缺点暴力法O(n×k)O(1)简单直观会超时优先队列O(n log k)O(k)实现简单remove操作慢单调队列O(n)O(k)最优解需要理解思想分块法O(n)O(n)另一种O(n)解法空间占用大推荐解法面试推荐单调队列法时间复杂度最优 O(n)空间复杂度 O(k)代码简洁优雅是这道题的标准解法常见问题答疑Q1为什么单调队列中存储索引而不是值A存储索引可以精确判断元素是否还在窗口内通过比较i - k避免重复值带来的歧义。Q2队列为什么要保持单调递减A保证队首始终是当前窗口的最大值。如果新元素比队尾大那么队尾元素永远不可能成为最大值因为新元素更大且更晚离开窗口可以直接淘汰。Q3处理重复元素时需要注意什么A使用而不是来比较这样新来的重复值会取代旧值避免窗口滑动时误删。相关题目推荐LeetCode 76. 最小覆盖子串LeetCode 1425. 带限制的子序列和LeetCode 1696. 跳跃游戏 VI总结滑动窗口最大值是一道经典的单调队列应用题。掌握单调队列的思想不仅能解决这道题还能解决一系列滑动窗口求最值的问题。核心要点使用双端队列维护单调递减序列队列存储索引而非值每次滑动时移除过期的队首、移除比新元素小的队尾、加入新元素队首就是当前窗口的最大值参考链接题目链接LeetCode 239. 滑动窗口最大值官方题解如果这篇文章对你有帮助欢迎点赞、收藏、关注