单调队列初步「建议收藏」

单调队列初步「建议收藏」
一直弄不明白单调队列是什么,在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。
我们从最简单的问题开始:
给定一个长度为N的整数数列a(i),i=0,1,…,N-1和窗长度k.
要求:
     f(i)=max{a(i-k+1),a(i-k+2),…,a(i)},i=0,1,…,N-1
问题的另一种描述就是用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值。
解法一:

大家好,又见面了,我是你们的朋友全栈君。

一直弄不明白单调队列是什么,在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。

我们从最简单的问题开始:

给定一个长度为N的整数数列a(i),i=0,1,…,N-1和窗长度k.

要求:

      f(i) = max{a(i-k+1),a(i-k+2),…, a(i)},i = 0,1,…,N-1

问题的另一种描述就是用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值。

解法一:

很直观的一种解法,那就是从数列的开头,将窗放上去,然后找到这最开始的k个数的最大值,然后窗最后移一个单元,继续找到k个数中的最大值。

这种方法每求一个f(i),都要进行k-1次的比较,复杂度为O(N*k)。

那么有没有更快一点的算法呢?

解法二:

我们知道,上一种算法有一个地方是重复比较了,就是在找当前的f(i)的时候,i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢?当然主要是i的前k-1个数中的最大值了。答案是可以,这就要用到单调递减队列。

单调递减队列是这么一个队列,它的头元素一直是队列当中的最大值,而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素,可以从队列的两端删除元素。

1.首先看插入元素:为了保证队列的递减性,我们在插入元素v的时候,要将队尾的元素和v比较,如果队尾的元素不大于v,则删除队尾的元素,然后继续将新的队尾的元素与v比较,直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2.队尾的删除刚刚已经说了,那么队首的元素什么时候删除呢?由于我们只需要保存i的前k-1个元素中的最大值,所以当队首的元素的索引或下标小于i-k+1的时候,就说明队首的元素对于求f(i)已经没有意义了,因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时,将队首元素删除。

 

从上面的介绍当中,我们知道,单调队列与队列唯一的不同就在于它不仅要保存元素的值,而且要保存元素的索引(当然在实际应用中我们可以只需要保存索引,而通过索引间接找到当前索引的值)。

为了让读者更明白一点,我举个简单的例子。

假设数列为:8,7,12,5,16,9,17,2,4,6.N=10,k=3.

那么我们构造一个长度为3的单调递减队列:

首先,那8和它的索引0放入队列中,我们用(8,0)表示,每一步插入元素时队列中的元素如下:

0:插入8,队列为:(8,0)

1:插入7,队列为:(8,0),(7,1)

2:插入12,队列为:(12,2)

3:插入5,队列为:(12,2),(5,3)

4:插入16,队列为:(16,4)

5:插入9,队列为:(16,4),(9,5)

。。。。依此类推

那么f(i)就是第i步时队列当中的首元素:8,8,12,12,16,16,。。。

程序代码如下:

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/153008.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • leetcode 颜色分类_LEETCODE

    leetcode 颜色分类_LEETCODE给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。示例 1:输入:nums = [2,0,2,1,1,0]输出:[0,0,1,1,2,2]示例 2:输入:nums = [2,0,1]输出:[0,1,2]示例 3:输入:nums = [0]输出:[0]示例 4:输入:nums = [1]输出:[1] 提示:n == num

  • 深入浅出URL编码

    深入浅出URL编码

  • oracle创建数据库文件时出错_oracle错误代码大全

    oracle创建数据库文件时出错_oracle错误代码大全一、创建数据库时报必须运行Netca以配置监听程序,然后才能继续。     解决方法:     1、停止Oracle该服务;    2、用系统管理员身份运行netmanager删除监听程序;    3、用netconfigurationassistant添加监听程序;    4、用系统管理员身份运行databaseconf…

  • java中notify作用_notify的过去式

    java中notify作用_notify的过去式用Java通知vsnotifyAllnotify和notifyAll方法之间有什么区别是棘手的Java问题之一,这很容易回答但是一旦访问者提出后续问题,你要么感到困惑,要么无法提供明确的答案?notify和notifyAll之间的主要区别在于notify方法只通知一个Thread,notifyAll方法将通知在该监视器上等待的所有线程或锁定。顺便说一句,这是你在各地阅读的内容,坦率地说,这句话…

  • pta集合相似度_结构相似度

    pta集合相似度_结构相似度原题链接输入样例:33 99 87 1014 87 101 5 877 99 101 18 5 135 18 9921 21 3输出样例:50.00%33.33%#include<bits/stdc++.h>#define x first#define y second#define send string::nopsusing namespace std;typedef long long ll;const int N = 1e4 + 10;cons

  • 使用JWT实现单点登录(完全跨域方案)

    首先介绍一下什么是JSONWebToken(JWT)?官方文档是这样解释的:JSONWebToken(JWT)是一个开放标准(RFC7519),它定义了一种紧凑且独立的方式,可以在各方之间作为JSON对象安全地传输信息。此信息可以通过数字签名进行验证和信任。JWT可以使用秘密(使用HMAC算法)或使用RSA或ECDSA的公钥/私钥对进行签名。虽然JWT可以加密以在各方之间提供保密…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号