本文写于 2020年02月23日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

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 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论