题目

本题与剑指 Offer 59 - I. 滑动窗口的最大值相同

给你一个整数数组 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]

示例 3：

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

示例 4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

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

思路

这道题并不复杂，但却是单调队列的经典题目。

先回答一个问题：如何求一个区间里的最大值呢？（这好像是废话），暴力一下不就得了。

那么根据题意，对于每个长度为 k 的滑动窗口，我们可以使用 O(k) 的时间遍历其中的每一个元素，找出其中的最大值。对于长度为 n 的数组 nums 而言，窗口的数量为 n-k+1，因此该算法的时间复杂度为 O((n−k+1)k)=O(nk)，会超出时间限制，因此我们需要进行一些优化。

现在我们知道了，问题的难点在于：如何在 O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。

方法一：单调队列（推荐）

单调队列其实很简单：就是一个「队列」，使用了一点巧妙的方法，使得队列中的元素单调递增（或递减）。

「单调队列」的核心思路和「单调栈」类似。队列的 push 方法依然是在队尾添加新元素，但是要把前面比新元素小的元素都删掉。
如果每个元素被加入时都这样操作，最终队列中的元素大小就会保持一个单调递减的顺序，并且队首元素即为「窗口」中的最大值。

因为这个队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

Java 没有直接支持单调队列，需要我们自己实现。

方法二：优先级队列

有的同学可能会想用一个大顶堆（优先级队列）来存放「窗口」里的 k 个数字，这样就可以知道这 k 个数的最大值是多少了。

对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动「窗口」时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在「窗口」中，在这种情况下，这个值在数组 nums 中的位置出现在「窗口」左边界的左侧。因此，当我们后续继续向右移动「窗口」时，这个值就永远不可能出现在「窗口」中了，我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素，直到其确实出现在「窗口」中。此时，堆顶元素就是「窗口」中的最大值。为了方便判断堆顶元素与「窗口」的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。

答案

Java

自定义单调队列

// 自定义队列
class MyQueue {
    Deque<Integer> deque = new LinkedList<>();

    // 弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    // 同时判断队列当前是否为空
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }

    // 添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    // 保证队列元素单调递减
    // 比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }

    // 队头元素始终为最大值
    int peek() {
        return deque.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 特例
        if (nums.length == 1) {
            return nums;
        }

        int len = nums.length - k + 1;
        // 存放结果元素的数组
        int[] result = new int[len];
        int index = 0;

        // 创建一个自定义队列
        MyQueue myQueue = new MyQueue();

        // 将前 k 个元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        // 取前 k 个元素的最大值
        result[index++] = myQueue.peek();

        // 循环处理剩余的元素
        for (int i = k; i < nums.length; i++) {
            // 滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
            myQueue.poll(nums[i - k]);
            // 滑动窗口加入最后面的元素
            myQueue.add(nums[i]);
            // 记录对应的最大值
            result[index++] = myQueue.peek();
        }
        return result;
    }
}

利用双端队列手动实现单调队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int len = nums.length;
        int[] result = new int[len - k + 1];
        int index = 0;

        for(int i = 0; i < len; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.pollFirst();
            }

            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.addLast(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                result[index++] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

优先级队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 边界条件 / 特殊情况
        if (nums.length == 0 || k == 0) return new int[0];

        int n = nums.length;

        // 为了方便判断堆顶元素与滑动窗口的位置关系
        // 我们在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                // 值是否相同？
                // 如果不同,则根据数值大小来判断权重
                // 如果相同,则根据索引大小来判断权重
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });

        // 将数组 nums 的前 k 个元素放入优先队列中
        for (int i = 0; i < k; ++i) {
            queue.offer(new int[]{nums[i], i});
        }

        // answer
        int[] ans = new int[n - k + 1];
        // 第一个结果 -> 数组 nums 的前 k 个元素中的最大值 -> 大根堆的堆顶元素
        ans[0] = queue.peek()[0];

        // 循环处理剩下的元素
        for (int i = k; i < n; ++i) {
            // 把一个新的元素放入优先队列中
            queue.offer(new int[]{nums[i], i});
            // 去除出现在滑动窗口左边界的左侧的值，因为这个值永远不可能出现在滑动窗口中了
            while (queue.peek()[1] <= i - k) {
                queue.poll();
            }
            // 向 answer 中写入当前滑动窗口内的最大值
            ans[i - k + 1] = queue.peek()[0];
        }

        return ans;
    }
}

总结

复杂度

看到这里，你可能会开始疑惑，push 操作中含有 while 循环，时间复杂度不是 O(1) 呀，那么本算法的时间复杂度应该不是线性时间吧？

单独看 push 操作的复杂度确实不是 O(1)，但是算法整体的复杂度依然是 O(N) 线性时间。要这样想，nums 中的每个元素最多被 push_back 和 pop_back 一次，没有任何多余操作，所以整体的复杂度还是 O(N)。

空间复杂度就很简单了，就是窗口的大小 O(k)。

「单调队列」和「优先级队列」

有的读者可能觉得「单调队列」和「优先级队列」比较像，实际上差别很大的。

单调队列在添加元素的时候靠删除元素保持队列的单调性，相当于抽取出某个函数中单调递增（或递减）的部分；而优先级队列（二叉堆）相当于自动排序，差别大了去了。

扩展

大家貌似对单调队列都有一些疑惑，首先要明确的是，题解中单调队列里的 pop 和 push 接口，仅适用于本题哈。

单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。不要以为本地中的单调队列实现就是固定的写法哈。

算法总纲

239. 滑动窗口最大值

题目

思路