嗯，查询滑动窗口最大值的这4种方法不错....

本文已收录至 Github《小白学算法》系列： https://github.com/vipstone/algorithm

这是一道比较基础的算法题，涉及到的数据结构也是我们之前讲过的，我这里先买一个关子。这道面试题最近半年在亚马逊的面试中出现过 28 次，在字节跳动中出现过 7 次，数据来源于 LeetCode。

我们先来看题目的描述。

题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

LeetCode： https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

题目解析

上面的题目看不懂？没关系，接下来来看这幅图可以清楚的描述这道题：

从上述图片可以看出，题目的意思为：给定一个数组，每次查询 3 个元素中的最大值，数量 3 为滑动窗口的大小，之后依次向后移动查询相邻 3 个元素的最大值。图片中的原始数组为 [1,3,-1,-3,5,3,6,7]，最终滑动窗口的最大值为 [3,3,5,5,6,7]。

看到这个题之后，我们的第一直觉就是暴力解法，用两层循环依次查询滑动窗口的最大值，实现代码如下。

实现方法 1：暴力解法

暴力解法的实现思路和实现代码很直观，如下所示：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[0];
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            // 初始化最大值
            int max = nums[i]; 
            // 循环 k-1 次找最大值
            for (int j = i + 1; j < (i + k); j++) {
                max = (nums[j] > max) ? nums[j] : max;
            }
            res[i] = max;
        }
        return res;
    }
}

把以上代码提交至 LeetCode，执行结果如下：

从上述结果可以看出，虽然代码通过了测试，但执行效率却很低，这种代码是不能应用于生产环境中的，因此我们需要继续找寻新的解决方案。

实现方法 2：改良版

接下来我们稍微优化一下上面的方法，其实我们并不需要每次都经过两层循环，我们只需要一层循环拿到滑动窗口的最大值（之前循环元素的最大值），然后在移除元素时，判断当前要移除的元素是否为滑动窗口的最大值，如果是，则进行第二层循环来找到新的滑动窗口的最大值，否则只需要将最大值和新增的元素比较大小即可，实现代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[0];
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        // 上一轮循环移除的值
        int r = -Integer.MAX_VALUE; 
        // 滑动窗口最大值（初始化）
        int max = r; 
        for (int i = 0; i < res.length; i++) {
            // 1.判断移除的值，是否为滑动窗口的最大值
            if (r == max) {
                // 2.移除的是滑动窗口的最大值，循环找到新的滑动窗口的最大值
                max = nums[i]; // 初始化最大值
                // 循环找最大值
                for (int j = i + 1; j < (i + k); j++) {
                    max = Math.max(max, nums[j]);
                }
            } else {
                // 3.只需要用滑动窗口的最大值和新增值比较即可
                max = Math.max(max, nums[i + k - 1]);
            }
            // 最终的返回数组记录
            res[i] = max;
            // 记录下轮要移除的元素
            r = nums[i];
        }
        return res;
    }
}

把以上代码提交至 LeetCode，执行结果如下：

从上述结果可以看出，改造之后的性能基本已经符合我的要求了，那文章开头说过这道题还可以使用我们之前学过的数据结构？那它说的是什么数据结构呢？

其实我们可以使用「队列」来实现这道题目，它的实现思路也非常简单，甚至比暴力解法更加方便，接下来我们继续往下看。

实现方法 3：优先队列

这个题的另一种经典的解法，就是使用最大堆的方式来解决，最大堆的结构如下所示：

最大堆的特性是堆顶是整个堆中最大的元素。

我们可以将滑动窗口的值放入最大堆中，这样利用此数据结构的特点（它会将最大值放到堆顶），因此我们就可以直接获取到滑动窗口的最大值了，实现代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[]{};
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        // 优先队列
        PriorityQueue<Integer> queue = new PriorityQueue(res.length, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                // 倒序排列（从大到小，默认是从小到大）
                return i2 - i1;
            }
        });
        // 第一轮元素添加
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        res[0] = queue.peek();
        int last = nums[0]; // 每轮要移除的元素
        for (int i = k; i < nums.length; i++) {
            // 移除滑动窗口之外的元素
            queue.remove(last);
            // 添加新元素
            queue.offer(nums[i]);
            // 存入最大值
            res[i - k + 1] = queue.peek();
            // 记录每轮要移除的元素（滑动窗口最左边的元素）
            last = nums[i - k + 1];
        }
        return res;
    }
}

代码解读

从上述代码可以看出：最大堆在 Java 中对应的数据结构就是优先级队列 PriorityQueue，但优先级队列默认的排序规则是从小到大进行排序的，因此我们需要创建一个 Comparator 来改变一下排序的规则（从大到小进行排序），之后将滑动窗口的所有元素放入到优先级队列中，这样我们就可以直接使用 queue.peek() 拿到滑动窗口的最大值了，然后再循环将滑动窗口的边缘值移除掉，从而解决了本道题目。

把以上代码提交至 LeetCode，执行结果如下：

PS：从上面的执行结果可以看出，使用优先队列的执行效率很低，这是因为每次插入和删除都需要重新维护最大堆的元素顺序，因此整个执行的效率就会很低。

实现方法 4：双端队列

除了优先队列之外，我们还可以使用双端队列来查询滑动窗口的最大值，它的实现思路和最大堆的实现思路很像，但并不需要每次在添加和删除时进行元素位置的维护，因此它的执行效率会很高。

双端队列实现思路的核心是将滑动窗口的最大值始终放在队首位置（也就是队列的最左边），将小于最大值并在最大值左边（队首方向）的所有元素删除。这个也很好理解，因为这些相对较小的值既没有最大值大，又在最大值的前面，也就是它们的生命周期比最大值还短，因此我们可以直接将这些相对较小的元素进行删除，如下图所示：

像以上这种情况下，我们就可以将元素 1 和元素 2 删掉。

双端队列实现查询滑动窗口最大值的流程分为以下 4 步：

移除最左边小于最大值的元素（保证滑动窗口的最大值在队首位置）；
从队尾向前依次移除小于当前要加入到队列元素的值（淘汰小值且生命周期短的元素）；
将新元素加入到队列末尾；
将最大值加入到最终结果的数组中。

实现代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[0];
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        // 存储的数据为元素的下标
        ArrayDeque<Integer> deque = new ArrayDeque();
        for (int i = 0; i < nums.length; i++) {
            // 1.移除左边超过滑动窗口的下标
            if (i >= k && (i - k) >= deque.peek()) deque.removeFirst();

            // 2.从最后面开始移除小于 nums[i] 的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                deque.removeLast();

            // 3.下标加入队列
            deque.offer(i);

            // 4.将最大值加入数组
            int rindex = i - k + 1;
            if (rindex >= 0) {
                res[rindex] = nums[deque.peek()];
            }
        }
        return res;
    }
}

把以上代码提交至 LeetCode，执行结果如下：