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

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));

    }
}