当前位置：首页 > news >正文

2025年- H27-Lc135- 239.滑动窗口最大值（自定义双端队列）---java版

news 2025/5/19 6:37:56

1.题目描述

在这里插入图片描述

2.思路

（1）双端队列可以移除最左边的元素，也可以移除最右边的元素（两端移除）
（2）在最右边插入元素（右边加入）
（3）队列单调性（保持队列是单调递减）
在这里插入图片描述

3.代码实现

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;public class H239 {public int[] maxSlidingWindow(int[] nums, int k) {//1.获取数组的长度int n=nums.length;//2.创建一个双端队列,存储的是数组的下标Deque<Integer> dq=new LinkedList<>();//3.// 初始化前 k 个元素，准备好第一个滑动窗口for(int i=0;i<k;i++) {//用while循环，队列不为空且当前元素nums[i]要大于队尾元素while (!dq.isEmpty() && nums[i]>=nums[dq.peekLast()]) {dq.pollLast(); //4.将队尾元素pop移出}//5. 将当前元素下标加入队尾，从队尾插入元素！！！！忘记了dq.offerLast(i);}//6.创建一个结果数组用来保存每次滑动窗口的最大值int[] res=new int[n-k+1];//7.结果数组的第一个元素是当前最大的元素。res[0]=nums[dq.peekFirst()];for(int i=k;i<n;++i){//8.判断队首元素是不是滑出当前的滑动窗口，判断队列的第一个元素是否过期，小于等于索引0 ，则移出while(!dq.isEmpty()&&dq.peekFirst()<=i-k){dq.pollFirst();}// 关键：移除所有小于当前元素的尾部元素!!!忘记了while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {dq.pollLast();}dq.offerLast(i);// 加入当前元素的下标//9.当前窗口的最大值就是队首元素对应的值，将每次滑动窗口的队首元素都加入到结果数组中。res[i-k+1]=nums[dq.peekFirst()];}//10.返回结果数组return res;}public static void main(String[] args){H239 test=new H239();int[] nums={1,3,-1,-3,5,3,6,7};int k=3;int[] res= test.maxSlidingWindow(nums,k);
//System.out.println("输出滑动窗口的最大值："+res); 不会输出数组内容.Java中直接打印数组会输出的是对象地址，比如 [I@5e2de80c。System.out.println("输出滑动窗口的最大值："+ Arrays.toString(res));}
}