算尽天下|算法|题解

[算尽天下系列第5期]LeetCode·293·滑动窗口最大值

凝神长老 · 2月23日 · 2020年 · · 344次已读

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 = 0nums = [],算一种特殊情况,要特别判断。

完整代码

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()]);
    }
}

0 0 投票
Article Rating
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论