个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要这篇文章详细讲解了滑动窗口最大值问题的解决方案。通过分析暴力解法和堆结构的局限性提出了使用单调队列的优化方法。文章深入剖析了单调队列的设计原理包括pop和push操作规则以及如何维护队列单调递减的特性。通过示例数组[1,3,-1,-3,5,3,6,7]和k3的动画演示直观展示了窗口滑动时队列的变化过程。最后给出了完整的Java代码实现包括处理边界条件和计算窗口个数的数学推导。这种单调队列的解法将时间复杂度优化到O(n)是处理滑动窗口最大值问题的高效方案。题目背景256.滑动窗口最大值这是刷题的第一个难题让我们一起看看吧给你一个整数数组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 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7示例 2输入nums [1], k 1输出[1]提示1 nums.length 105-104 nums[i] 1041 k nums.length题目分析这是使用单调队列的经典题目。难点是如何求一个区间里的最大值呢 这好像是废话暴力一下不就得了。暴力方法遍历一遍的过程中每次从窗口中再找到最大的数值这样很明显是O(n × k)的算法。有的同学可能会想用一个大顶堆优先级队列来存放这个窗口里的k个数字这样就可以知道最大的最大值是多少了但是问题是这个窗口是移动的而大顶堆每次只能弹出最大值我们无法移除其他数值这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。此时我们需要一个队列这个队列呢放进去窗口里的元素然后随着窗口的移动队列也一进一出每次移动之后队列告诉我们里面的最大值是什么。这个队列应该长这个样子class MyQueue { public: void pop(int value) { } void push(int value) { } int front() { return que.front(); } };每次窗口移动的时候调用que.pop(滑动窗口中移除元素的数值)que.push(滑动窗口添加元素的数值)然后que.front()就返回我们要的最大值。然后再分析一下队列里的元素一定是要排序的而且要最大值放在出队口要不然怎么知道最大值呢。但如果把窗口里的元素都放进队列里窗口移动的时候队列需要弹出元素。那么问题来了已经排序之后的队列 怎么能把窗口要移除的元素这个元素可不一定是最大值弹出呢。大家此时应该陷入深思.....其实队列没有必要维护窗口里的所有元素只需要维护有可能成为窗口里最大值的元素就可以了同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列即单调递减或单调递增的队列。对于窗口里的元素{2, 3, 5, 1 ,4}单调队列里只维护{5, 4} 就够了保持单调队列里单调递减此时队列出口元素就是窗口里最大元素。此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢设计单调队列的时候pop和push操作要保持如下规则pop(value)如果窗口移除的元素value等于单调队列的出口元素那么队列弹出元素否则不用任何操作push(value)如果push的元素value大于入口元素的数值那么就将队列入口的元素弹出直到push元素的数值小于等于队列入口元素的数值为止保持如上规则每次窗口移动的时候只要问que.front()就可以返回当前窗口的最大值。为了更直观的感受到单调队列的工作过程以题目示例为例输入: nums [1,3,-1,-3,5,3,6,7], 和 k 3动画如下那么我们用什么数据结构来实现这个单调队列呢使用deque最为合适在文章栈与队列来看看栈和队列不为人知的一面 (opens new window)中我们就提到了常用的queue在没有指定容器的情况下deque就是默认底层容器。代码流程解析自定义MyQueue类poll(val)只有当要移除的元素等于队头元素时才弹出说明该最大值即将离开窗口核心问题滑动窗口在移动时会移除窗口最左边的元素。但队列里存的不一定是这个元素因为也有可能这个元素在添加的时候就被淘汰了。举例说明假设nums [3,1,2,5]k 2第一步第一个窗口[3,1]添加 3队列[3]添加 11 比 3 小直接加 → 队列[3,1]窗口最大值 3第二步窗口右移移除 3加入 2现在窗口是[1,2]关键要移除的是nums[0] 3但当前队列是[3,1]队头deque.peek() 3执行poll(3)java if (!deque.isEmpty() 3 3) { // 相等 deque.poll(); // 弹出队头的 3 }add(val)从尾部移除所有比新元素小的元素保证单调递减这里添加元素的过程是核心逻辑我们在添加的时候要和队尾的元素进行比较如果大于队尾元素直接弹出队尾我们这里的队列维护的是最大值和所有可能成为下一次移动的最大值的元素因此如果新添加的元素已经大于存在的队友直接弹出然后继续进行比较新的队尾知道队列为空或者遇到比新元素大的元素然后把新元素加进队尾。假设nums [3,1,2,5]看add的执行过程插入 3队列空 → 不进入 while直接添加 →[3]插入 11 3❌ 不成立直接添加 →[3, 1]插入 2队列[3, 1]deque.getLast() 12 1✅ 成立 →removeLast()→ 移除 1队列变成[3]再次检查2 3❌ 不成立添加 2 →[3, 2]为什么移除 1因为 1 在 2 的前面且比 2 小。当 2 存在时窗口最大值永远不可能是 1要么是 3要么是 2所以 1 是冗余的。想象运动员排队队头是当前冠军最大值新来的运动员如果比队尾强队尾就被淘汰因为他们永远赢不了新人最后新运动员站到队尾peek()返回当前窗口最大值这里没什么好说的栈顶元素始终是最大值maxSlidingWindow方法先处理第一个窗口前 k 个元素记录最大值滑动窗口移除窗口最左边的元素 加入新元素 → 记录新最大值res[num] myQueue.peek()这里num初始值是 0这是第一个窗口的最大值。这里我们先确定第一个窗口为下面移动的起始范围做准备因为窗口是k起始索引是0所以第一个窗口是0到k-1后面的起始位置就是k下面进行移动操作k到最后我们这里循环的起始位置是k因为遍历的是nums[k],nums[k1],nums[k2], ...,nums[n-1]因为我们第一个位置的最大值已经找到也就是说0到k-1这第一个窗口已经处理完了后面我们通过循环来处理后面的窗口然后我们进行移动的时候左边会失去一个元素右边要添加一个元素但这个元素不是直接弹出的也就是我们上面的poll方法。如果离开的元素正好是当前队列的最大值在队头就把它弹出如果离开的元素不是最大值早就被淘汰了就什么都不做// 调用时把要移出的那个元素的值传进去 myQueue.poll(nums[i - k]); // nums[i-k] 是一个整数比如 3 // 在 MyQueue 内部 void poll(int val) { // val 接收的就是这个整数比如 3 if (!deque.isEmpty() val deque.peek()) { // 拿 3 和队头的值比较 deque.poll(); // 相等才移除队头 } }if (nums.length 1) { return nums; }作用处理数组只有一个元素的特殊情况。为什么需要当数组长度为 1 时滑动窗口长度 k 只能是 1因为 k ≤ nums.length结果数组长度 1 - 1 1 1最大值就是这唯一的元素是否必须不是必须的但可以避免后续循环的麻烦java // 如果不加这个判断下面代码也能正常工作 int len nums.length - k 1; // len 1 int[] res new int[len]; // res 长度 1 // 第一个 for 循环i k → i 1 → 添加 nums[0] // res[num] myQueue.peek() → res[0] nums[0] // 第二个 for 循环i k → i 1, i nums.length? 1 1? false → 不执行 // 返回 [nums[0]] ✅所以这行可以省略但加上可以让代码意图更清晰。int len nums.length - k 1;作用计算结果数组的长度也就是滑动窗口的个数。公式推导数组长度n nums.length窗口大小k窗口个数 能滑动的次数 1具体计算text窗口起始位置可以从 0 到 n-k所以窗口个数 (n-k) - 0 1 n - k 1举例验证数组长度 n窗口大小 k窗口个数计算8368-3165155-1155515-5111111-111整体流程概览text初始化 → 处理第一个窗口 → 滑动窗口 → 返回结果关键对应关系当前窗口要移除的元素要加入的元素[0,1,2]nums[0]nums[3][1,2,3]nums[1]nums[4][2,3,4]nums[2]nums[5].........题目答案//解法一 //自定义数组 class MyQueue { DequeInteger deque new LinkedList(); //弹出元素时比较当前要弹出的数值是否等于队列出口的数值如果相等则弹出 //同时判断队列当前是否为空 void poll(int val) { if (!deque.isEmpty() val deque.peek()) { deque.poll(); } } //添加元素时如果要添加的元素大于入口处的元素就将入口元素弹出 //保证队列元素单调递减 //比如此时队列元素3,12将要入队比1大所以1弹出此时队列3,2 void add(int val) { while (!deque.isEmpty() val deque.getLast()) { deque.removeLast(); } deque.add(val); } //队列队顶元素始终为最大值 int peek() { return deque.peek(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length 1) { return nums; } int len nums.length - k 1; //存放结果元素的数组 int[] res new int[len]; int num 0; //自定义队列 MyQueue myQueue new MyQueue(); //先将前k的元素放入队列 for (int i 0; i k; i) { myQueue.add(nums[i]); } res[num] myQueue.peek(); for (int i k; i nums.length; i) { //滑动窗口移除最前面的元素移除是判断该元素是否放入队列 myQueue.poll(nums[i - k]); //滑动窗口加入最后面的元素 myQueue.add(nums[i]); //记录对应的最大值 res[num] myQueue.peek(); } return res; } }补充我们这里是自定义队列来实现的还有另一种直接用双向队列其实逻辑都是一样的实现起来还更简单对比项解法一解法二队列类型LinkedList实现DequeArrayDeque实现Deque存储内容数值下标是否封装是自定义MyQueue类否直接操作移除过期比较数值val peek()比较下标peek() i-k1底层实现链表循环数组性能更好//利用双端队列手动实现单调队列 /** * 用一个单调队列来存储对应的下标每当窗口滑动的时候直接取队列的头部指针对应的值放入结果集即可 * 单调递减队列类似 head -- 3 -- 2 -- 1 -- 0 (-- tail) (左边为头结点元素存的是下标) */ class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ArrayDequeInteger deque new ArrayDeque(); int n nums.length; int[] res new int[n - k 1]; int idx 0; for(int i 0; i n; i) { // 根据题意i为nums下标是要在[i - k 1, i] 中选到最大值只需要保证两点 // 1.队列头结点需要在[i - k 1, i]范围内不符合则要弹出 while(!deque.isEmpty() deque.peek() i - k 1){ deque.poll(); } // 2.维护单调递减队列新元素若大于队尾元素则弹出队尾元素直到满足单调性 while(!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offer(i); // 因为单调当i增长到符合第一个k范围的时候每滑动一步都将队列头节点放入结果就行了 if(i k - 1){ res[idx] nums[deque.peek()]; } } return res; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励