【LC100】No.239. 滑动窗口最大值

题目描述

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

返回 滑动窗口中的最大值 。

提示:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

• 1 <= k <= nums.length

示例

示例 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]

链接

思路

做不出来。

题目译为“在 k 长的窗口动态滑动的过程中，维护最大值”。

滑动窗口的性质是，当窗口滑动时，右侧增加一个新元素，左侧移除一个旧元素。

由于是找最大值，如果新加入的元素比窗口中的部分旧元素大，那么这部分旧元素在后续滑动中永远不可能成为最大值，因为新元素更大且存在时间更长比这些旧的更长。

因此，我们需要：

• 根据窗口右端新元素和窗口内旧元素的大小，移除这些无用的旧元素。

• 在窗口滑动中，从窗口左端移除因为窗口长度固定而离开窗口的旧元素。

两端都需要操作，我们可以想到双端队列，维护一个"候选最大值"队列。

每次新元素加入时，所有比它小的旧元素都被移除，那么这个队列单调递减——也可以称为“单调双端队列”。

此时题目的运行过程变为：

1. 入队：每次窗口右端元素入队时，移除所有小于等于它的元素，之后将它入队。

2. 出队：判断此时队列最左端元素是否从窗口左端滑出了窗口。

3. 计算值：此时队列的队首元素即为当前窗口的最大值。

由于需要判断队首元素是否滑出窗口，所以队列里需要存储下标，否则无法判断队首元素的下标和当前窗口最左端的下标的大小。

至于结果数组的大小，相当于是数组第 k 个元素到最末尾元素（第 nums.length 个）之间的元素个数，由于 k 和末尾都需要算入，因此是闭区间，所以为 nums.length - k + 1。

同理，计算窗口左端下标 left 时，相当于是闭区间 [lefft, i] 有 k 个元素，所以是 i - k + 1。

解法一：双端队列

Q：为什么第二步出队时，移除队首元素用 if 不用 while。

A：因为对于每次循环，就是每个 i 来说，都是入队元素之后就马上判断队首是否滑出了窗口，如果发现则当即移除，所以每次循环只需要使用 if 出队一次。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        int len = nums.length;
        // 闭区间[k, len]
        int[] res = new int[len - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast();
            }
            q.addLast(i);
            // 窗口左侧元素下标
            int left = i - k + 1;
            if (q.getFirst() < left) {
                q.removeFirst();
            }
            if (left >= 0) {
                res[left] = nums[q.getFirst()];
            }
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

解法二：用数组实现双端队列

双端队列中的一些函数确实不好记。

我们也可以用数组来实现一个双端队列，只需要 head 和 tail 两个指针指向首尾即可。

tail 初始化取 -1 的原因：

1. tail != head 表示队列为空。

2. 避免单独判断队列为空的情况。（取 0 也行，第一次添加时需要单独判断 tail 是否为 0，是的话不需要 tail++，直接 q[tail] = i 即可。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        int len = nums.length;
        int[] res = new int[len - k + 1];
        // 用数组来表示双端队列，存队列下标
        int[] q = new int[len];
        int head = 0, tail = -1;
        for (int i = 0; i < len; i++) {
            while (tail >= head && nums[q[tail]] <= nums[i]) {
                tail--;
            }
            tail++;
            q[tail] = i;
            int left = i - k + 1;
            if (q[head] < left) {
                head++;
            }
            if (left >= 0) {
                res[left] = nums[q[head]];
            }
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)