关于力扣第239题的题解【滑动窗口最大值】

摘要：本文详细解析力扣第 239 题「滑动窗口最大值」的解法，核心思路是采用滑动窗口 + 单调队列。遍历数组时，我们维护一个双端队列（Deque），并始终保持队首为当前窗口的最大值。每当加入新元素前，先移除队尾所有比它小的元素，使队列保持单调递减；同时剔除已滑出窗口的队首元素，从而在 O(n) 时间内求出每个窗口的最大值。文中附有完整的 Java 代码实现，并整理了 Deque 常用方法对照表，帮助读者快速掌握单调队列的写法与原理。

关于力扣第239题的题解【滑动窗口最大值】

classSolution{publicint[]maxSlidingWindow(int[]nums,intk){int[]res=newint[nums.length+1-k];Deque<Integer>queue=newLinkedList();for(inti=0;i<nums.length;i++){// ① 移除队尾所有比当前元素小的元素while(!queue.isEmpty()&&nums[queue.peekLast()]<nums[i]){queue.pollLast();// 从队尾移除}// ② 将当前索引加入队尾queue.offerLast(i);// ③ 移除窗口外的队首元素if(queue.peek()<i+1-k){queue.poll();// 从队首移除}// ④ 记录窗口最大值if(i+1>=k){res[i+1-k]=nums[queue.peek()];// 队首就是最大值}}returnres;}}

本题使用的是滑动窗口+队列的解法，首先直接遍历整个数组，当遇到一个当前元素比之前的元素大时，这个元素一定是当前窗口的最大值，那么就可以直接把之前的元素全都移除，并将这个元素作为新的队尾元素。
而当位于队友的元素也就是数组下标已经离开窗口范围的时候，应该直接移除该元素，并且之后最大的元素一定是队首【因为每次加入新元素时，都会判断一次，如果新元素大于队首，就一定会把原来的队首移除，如果没有顶替原来的队首，那么新元素一定比队首小。】

以下是队列的基础代码