LeetCode100之滑动窗口最大值(239)--Java

1.问题描述

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

        示例1

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

        示例2 

输入：nums = [1], k = 1
输出：[1]

        提示

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

        难度等级

                困难

        题目链接

           滑动窗口的最大值

2.解题思路

        这道题要我们求滑动窗口的最大值，也就是窗口内最大的那个数，一开始我的想法是确定窗口之后，再用一个for循环来遍历，找出里面的最大值，我一开始就是这么做的，可以通过，但是耗时很长，和我接下来要提供的这种方法，在时间上相差了10倍左右。

        这道题我们可以采用双端队列来进行解题。我们都知道，队列有先进先出的特点，而滑动窗口在移动的过程中，也是先进先出，很符合队列的特点，那为什么是采用双端队列呢？因为我们要找到的是滑动窗口的最大值，所以我们要保证队列中的元素是递减的，这样队头的元素就是我们要的最大值，为了保证队头的元素是递减的，我们从队尾放入元素的时候，就必需能够把队尾的元素取出来，而双堆队列正好符合了我们的需求，它可以从队头取元素，也可以从队尾取元素。

            //双端队列
            Deque<Integer> queue = new LinkedList<>();

        解决了为什么时候双端队列之后，我们就可以开始初始化存储答案的数组和双端队列了，将题目所给数组的第一个索引存入队列中，便于后续的遍历。同时定义一个指针p，用来向存储答案的数组存入元素。

        //存储答案
        int[] data = new int[nums.length - k + 1];
        //初始化队列
        queue.offer(0);
        int p =0;

        接着，我们就可以开始遍历了。首先，我们需要先将队列中已经不在滑动窗口内的元素索引移除(i - k + 1)是滑动窗口最左边的索引，若队头索引比(i-k+1)小的话，那已经不在滑动窗口内部了，将队友索引移除，在移除之前，我们得先加一个判断队列是否为空的操作，避免出现越界的情况。(这一部分的操作相当于是改变滑动窗口的左边界。)

            //移除不在窗口内的元素(队列头)
            while(!queue.isEmpty() && queue.peekFirst() < i -k +1){
                queue.pollFirst();
            }

        然后，我们就可以来改变滑动窗口的右边界了。前面我们提到，我们要确保队列里的元素是递减的，其实指的是队列里的索引指向的数组中的元素是要递减的。所以我们在往队列中添加元素之前，需要想把队列尾中小于我们要添加的索引对应的元素移除，才能保证递减的要求。用一个循环不断的比较移除，直到遇到比自己大的元素之后，我们就可以把当前索引存入队列当中了。(这一部分操作相当于是改变滑动窗口的右边界。)

            //保持窗口内的元素递减(队列尾)，确保队列中的元素是递减的
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
                queue.pollLast();
            }
            //添加元素索引
            queue.offer(i);

        左右边界都改变之后，就实现了滑动。最后，我们只需要将队列头的索引对应的数组元素存放到答案数组中即可。注意：当滑动窗口的大小到达为k之前(i >= k-1)，是不存在什么窗口内的最大值的，所以如果窗口还没到达最大时，不用进行添加最大值的操作。

            //窗口的大小满足k后才能寻找最大值
            if(i >= k -1){
                data[p++] = nums[queue.peekFirst()];
            }

        重复上述操作，知道整个数组遍历完成之后，我们就找到了各个窗口中的最大值了，直接返回即可。

3.代码展示

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //存储答案
        int[] data = new int[nums.length - k + 1];
        //双端队列
        Deque<Integer> queue = new LinkedList<>();
        //初始化队列
        queue.offer(0);
        int p =0;
        for(int i = 0;i < nums.length;i++){
            //移除不在窗口内的元素(队列头)
            while(!queue.isEmpty() && queue.peekFirst() < i -k +1){
                queue.pollFirst();
            }
            //保持窗口内的元素递减(队列尾)，确保队列中的元素是递减的
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
                queue.pollLast();
            }
            //添加元素索引
            queue.offer(i);
            //窗口的大小满足k后才能寻找最大值
            if(i >= k -1){
                data[p++] = nums[queue.peekFirst()];
            }
        }
        return data;
    }
}

4.总结

        这道题用暴力的方法也是可以解决的，但是我觉得采用双端队列来解决会更好。使用双端队列解题的难点，在于要记得及时将已经不在窗口内的元素移除和在添加新元素索引之前，要把无法保持递减的元素索引移除。好了，这道题就讲到这了，祝大家刷题愉快！