字串-239. 滑动窗口最大值

张开发
• 2026/4/4 17:20:26 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

字串-239. 滑动窗口最大值
文章目录1.题解核心思路单调双端队列2.机考代码3.知识点讲解1.双端队列核心知识点1. 核心定义2.本题所用方法2.队列1. 队首front / 头2. 队尾rear / 尾力扣地址 困难239. 滑动窗口最大值1.题解核心思路单调双端队列这道题的最优解法是维护一个单调递减的双端队列Deque核心逻辑如下队列存索引不存值队列中只存储数组元素的下标保证队列对应的元素值是严格单调递减的队首永远是当前窗口的最大值下标。窗口左边界维护当队首下标超出当前窗口的左边界i - k 1时从队首弹出。队列单调性维护新元素入队前从队尾弹出所有比它小的元素这些元素不可能成为后续窗口的最大值再将新元素下标入队。收集结果当窗口形成i - k 1 0时队首对应的元素就是当前窗口的最大值加入结果数组。classSolution{publicint[]maxSlidingWindow(int[]nums,intk){intnnums.length;int[]resnewint[n-k1];DequeIntegerdqnewLinkedList();for(inti0;in;i){while(!dq.isEmpty()i-dq.peekFirst()1k)dq.pollFirst();while(!dq.isEmpty()nums[dq.peekLast()]nums[i])dq.pollLast();dq.addLast(i);if(i-k10)res[i-k1]nums[dq.peekFirst()];}returnres;}}2.机考代码importjava.util.Deque;importjava.util.LinkedList;importjava.util.Scanner;publicclassMain{publicstaticint[]maxSlidingWindow(int[]nums,intk){intnnums.length;int[]resnewint[n-k1];// 双端队列存储数组下标保证队列对应元素单调递减DequeIntegerdqnewLinkedList();for(inti0;in;i){// 1. 维护窗口左边界队首下标超出窗口范围弹出while(!dq.isEmpty()i-dq.peekFirst()1k)dq.pollFirst();// 2. 维护队列单调性队尾元素比当前元素小弹出不可能成为最大值while(!dq.isEmpty()nums[dq.peekLast()]nums[i])dq.pollLast();// 3. 当前元素下标入队dq.addLast(i);// 4. 窗口形成后收集最大值队首元素if(i-k10)res[i-k1]nums[dq.peekFirst()];}returnres;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 读取数组长度intnsc.nextInt();int[]numsnewint[n];// 读取数组元素for(inti0;in;i){nums[i]sc.nextInt();}// 读取目标值intksc.nextInt();// 输出结果for(inti:maxSlidingWindow(nums,k)){System.out.print(i );}}}3.知识点讲解1.双端队列核心知识点1. 核心定义DequeIntegerdequenewLinkedList();DequeJava 中的双端队列接口支持在队列的头部和尾部进行插入、删除操作是实现「单调队列」的核心容器。LinkedListDeque接口的最常用实现类底层是双向链表头尾操作时间复杂度都是O(1)完美适配本题需求。2.本题所用方法操作Java 写法判空deque.isEmpty()取队首不删deque.peekFirst()删队首deque.pollFirst()取队尾不删deque.peekLast()删队尾deque.pollLast()队尾入队deque.offerLast(i)2.队列我画个文字版队列给你看队首 (front) 队尾 (rear) ↓ ↓ [ 小明 ] → [ 小红 ] → [ 小刚 ] → [ 小李 ]1. 队首front / 头队列最前面的元素第一个进来的第一个出去的出队删除元素只能从队首删2. 队尾rear / 尾队列最后面的元素最后一个进来的入队添加元素只能从队尾加

更多文章