滑动窗口的最大值

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

分析

滑动的窗口中总是有固定个数的元素，其实可以视为是一个队列，每个滑动一个单位可以看做队首出队并且后一个元素入队的过程，通过这样的方法就可以使用队列的最大值作为解题方法，使用队列的最大值解法在来做这一道困难算法，就会变得非常简单，完成后，这道题的中心就只需要方法处理边界条件上了。

代码

使用定义好的最大值队列数据结构只需要调用方法即可，这里放一个直接套入队列的代码，比较笨重，可读性也非常差，不建议使用，大家也可以在代码的基础上对方法进行封装，使用更加便利

public int[] maxSlidingWindow(int[] nums, int k) {
        //边界条件处理过程
        int length = nums.length;
        if (length == 0){
            return new int[0];
        }

        if (length == 1){
            return nums;
        }
        
        int[] res = new int[length - k + 1];

        //直接在方法中嵌套队列最大值数据结构
        Queue<Integer> main = new LinkedList<>();
        Deque<Integer> support = new LinkedList<>();

        //进入这里是窗口元素至少为2的情况，最开始判断的是左边界，通过单独初始化第一个窗口可以直接避免右边界的确定
        main.offer(nums[0]);
        support.offer(nums[0]);

        for (int i = 1; i < k; i++) {
            while(!support.isEmpty() && support.peekLast() < nums[i]){
                support.pollLast();
            }
            support.offerLast(nums[i]);
            main.offer(nums[i]);
        }

        res[0] = support.peekFirst();

        //接下来从第二个窗口开始以及往后确定最大值的过程
        int sign = 1;
        for (int i = k; i < length; i++) {
            if (main.poll().equals(support.peekFirst())){
                support.pollFirst();
            }

            while(!support.isEmpty() && support.peekLast() < nums[i]){
                support.pollLast();
            }
            support.offerLast(nums[i]);
            main.offer(nums[i]);

            res[sign] = support.peekFirst();
            sign++;
        }
        return res;
    }