Visits: 229

LeetCode 293 滑动窗口最大值

题目描述

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

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

提示：

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

进阶：

你能在线性时间复杂度内解决此题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum

样例

样例输入

1 3 -1 -3 5 3 6 7
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 个步骤，第一个是把不在窗口中的元素移除，第二个是把不符合限定条件的元素移除。

void maintainDequeue(int i) {
    // 对于已经不在窗口范围内的 i，移除
    while (!deq.isEmpty() && deq.getFirst() <= i - k ) {
        deq.pollFirst();
    }
    // 遍历队列中的元素，如果队列中元素的值比当前值还要小，则无论如何滑动窗口，那个值不可能成为最大值，移除
    while (!deq.isEmpty() && nums[deq.getLast()]  < nums[i]) {
        deq.pollLast();
    }
}

然后操作就分为两步，第一步是维护初始队列，第二步是逐步遍历剩余元素并维护队列。

// 遍历前 k 个元素，初始化双端队列，并记录最大下标
        for (int i = 0; i < k; i++) {
            maintainDequeue(i);
            deq.addLast(i);
            if (nums[maxIndex] < nums[i]) {
                maxIndex = i;
            }
        }
        ans.add(nums[maxIndex]);

至此，双端队列已经完成初始化，maxIndex 之后不会用到了，之后要么 getFirst 的下标超过了窗口范围被移除，要么 getLast 比当前元素小被移除，因此始终判断 getFirst 就是每一次窗口中最大元素的位置。

for (int i = k; i < nums.length; i++) {
    maintainDequeue(i);
    deq.addLast(i);
    assert !deq.isEmpty();
    ans.add(nums[deq.peekFirst()]);
}

最后有一个非常坑的地方，k = 0 且 nums = []，算一种特殊情况，要特别判断。

完整代码

private static void maintainDequeue(int i) {
    // 对于已经不在窗口范围内的 i，移除
    while (!deq.isEmpty() && deq.getFirst() <= i - k ) {
        deq.pollFirst();
    }
    // 遍历队列中的元素，如果队列中元素的值比当前值还要小，则无论如何滑动窗口，那个值不可能成为最大值，移除
    while (!deq.isEmpty() && nums[deq.getLast()]  < nums[i]) {
        deq.pollLast();
    }
}
 public static void main(String[] args) {

    ArrayList<Integer> ans = new ArrayList<>();
    // 遍历前 k 个元素，初始化双端队列，并记录最大下标
    for (int i = 0; i < k; i++) {
        maintainDequeue(i);
        deq.addLast(i);
        if (nums[maxIndex] < nums[i]) {
            maxIndex = i;
        }
    }
    ans.add(nums[maxIndex]);
    // 至此，双端队列已经完成初始化，maxIndex 之后不会用到了
    // 之后要么 getFirst 的下标超过了窗口范围被移除，要么 getLast 比当前元素小被移除
    // 因此始终判断 getFirst 就是每一次窗口中最大元素的位置
    for (int i = k; i < nums.length; i++) {
        maintainDequeue(i);
        deq.addLast(i);
        assert !deq.isEmpty();
        ans.add(nums[deq.peekFirst()]);
    }
}