数据结构之单调栈、单调队列

今天学习了单调栈还有单调队列的概念和使用,接下来我将对其定义并配合几道习题进行讲解:

首先先来复习一下栈与队列:

然后我们来看一下单调栈的定义:
单调栈中的元素从栈底到栈顶的元素的大小是按照单调递增或者单调递减的关系进行排列的,由于它的这个性质可以方便我们解决很多问题,接下来看一道可以用这个单调栈来解决的例题:

接下来我会提供两个不同的代码 但其实本质一样的解答,我们可以用样例模拟一下过程,这里我们考虑用一个单调递减的栈进行解答:

首先2进栈,然后接下来是6进栈,首先我们判断出6比2大,那么2对应的答案就是6的下标2并将2出栈,接下来3 1依次进栈,他们两个都满足递减,接下来5进栈之后,5对应的下标就是3 1两个的答案,并将这两个出栈,这样一直模拟下去就会得到每一个的答案,接下来上代码(从左往右看):

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int a[N],top,ans[N],n,s[N];
int main(){//先完成所有的输入cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//这里就是本题的模拟过程for(int i=1;i<=n;i++){//我们这个时候栈即将进来一个元素,这时候我们将这个元素与单调递减栈中元素从上往下进行比较while(top && a[i]>a[s[top]]){//如果满足while循环条件,也就是即将进站元素大于栈顶元素,那么栈顶元素对应的答案下标就是即将进栈元素的下标ans[s[top]]=i;//将栈顶元素出栈--top;}//将这个元素进栈s[++top]=i;}//最后由于会有后面不存在比他更大的元素,这时候把他们都设置为0for(int i=1;i<=top;i++)ans[s[i]]=0;//逐个输出for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

上面的代码我附着了详细的讲解 

这里其实也可以从右往左进行枚举并同样使用单调栈进行解答,代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,top,a[N],s[N],ans[N];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//从右往左进行模拟for(int i=n;i;i--){//当栈非空并且栈顶元素是小于即将进栈的元素时将栈顶元素去除while(top && a[s[top]]<=a[i])--top;//如果栈非空,则说明这时候栈顶元素就是大于此时即将进栈元素的第一个元素if(top) ans[i]=s[top];else ans[i]=0;//否则就没有比他更大的数s[++top]=i;//入栈}//逐个输出for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

接下来看第二道题目:

最大矩形面积:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int a[N],top,l[N],r[N],n,s[N];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//从左往右计算每个位置左边第一个比他矮的for(int i=1;i<=n;i++){while(top && a[i]<=a[s[top]])--top;if(top) l[i]=s[top];else l[i]=0;s[++top]=i;}//清空栈top=0;//从右往左模拟计算每个数字右边第一个高度小于它的位置for(int i=n;i;i--){if(top && a[i]<=a[s[top]])	--top;if(top) r[i]=s[top];else r[i]=n+1;//入栈s[++top]=i;}long long ans=0;//计算最大的矩形面积for(int i=1;i<=n;i++)ans=max(ans,1LL*a[i]*(r[i]-l[i]-1));cout<<ans<<endl;return 0;
}

第三题的难度较大:数对统计

接下来我会给出代码并附着具体的思路以及分析:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n;
int a[N],s[N],top,ans;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];/*上面是输入部分*//*接下来我们分析一下题目 题目共有n个不同的数字,我们要求出有多少个数对i,j在i,j中之间的元素不存在大于边界的元素的数对个数我们可以分析首先挨着的两个数字都能达到这样的条件,因为他俩之间一个数字都没有然后我们考虑当有三个及以上数字的数对的时候,中间的所有元素都不能大于两边,这里就是我们运用单调栈解答的关键思路*/for(int i=1;i<=n;i++){/*下标为i的元素即将进栈*/while(top && a[i]>=s[top]){/*将即将进栈的元素与栈顶元素作大小的对比如果大于栈顶元素,那么以栈顶元素开始的数对i,满足条件的j的数对的终点最长也就是此时即将进栈的元素,因此移除栈顶元素并让答案加一*/--top;++ans;}if(top) ++ans;//这里如果栈顶还有元素的话,说明这个栈顶的元素是大于即将进栈的元素的,那么他们之间的所有元素与以栈顶元素还有即将进栈的元素组成的数对满足条件s[++top]=a[i];/*上述for循环中 我们考虑的是运用一个单调栈来模拟一个答案数量的增加过程*/cout<<ans<<endl;//输出答案return 0; 
}

接下来看单调队列:

定义:队列中的元素按照递增或者递减的线性关系排列的队列。

利用队列先进先出的特点以及单调队列的特质可以用来解决很多的问题,接下来看例题:

1.动态区间的最大数:

这个题目我们考虑用一个单调递减的队列进行解答:

我们可以维护队首元素是最大的数字,他就是每个m长度区间的答案,然而他最多只可能连续被输出m次,因为无论多大,队列的长度最大同时只能是m,总的来说我们需考虑下面三个问题:

 

 接下来上代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,m;
int a[N],q[N],front=1,rear=0;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];/*接下来是代码的精华部分*/for(int i=1;i<=n;i++){while(front<=rear && a[q[rear]]<=a[i])//当队列非空并且即将入队的元素是大于队尾元素的时候--rear;	//由于要维护一个单调递减的队列,所以这个时候需要将队尾元素暂时性出队q[++rear]=i;//将对应的元素下标入队/*这里想说明一点就是当前子队列的下标是从front开始到i的,虽然中间会更换队尾的元素以便于维护单调队列的单调性,但是右边界始终就是i*/if(m<i-q[front]+1) ++front;//当队列的长度大于m的时候,将队首元素出队,这时候的最大值应该是后面队列中进行挑选了if(i>=m) cout<<a[q[front]]<<' ';//输出每个对应的动态区间的最大值}return 0;
}

接下来看这道题的模板:

 接下来看第二道例题:

接下来附上代码以及讲解:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,m,a[N],s[N],q[N],front=1,rear=0,l,r;
int main(){cin>>n>>l>>r;s[0]=0;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}// 上面完成所有的输入并且利用s数组来计算出所有的前缀和int x=l,ans=-1<<30;//将x的长度初始值设置成为最短的区间长度l并且由于a数组中的元素可能都为负数那么我们一开始的默认ans需要设置的很小以便于应付极端情况这里的x其实也就是区间的右端点//接下来从1开始进行枚举并通过维护一个单调递减的队列,其中存储的是前缀和数组的下标for(int i=1;i+l-1<=n;i++){//请注意这里的i其实是区间和的左端点,队列中我们存储的都是前缀和数组的下标while(x<=i+r-1 && x<=n){//这个x是用来维护一个长度为l到r的并且小于数组长度n的一个区间长度while(front <= rear && s[q[rear]]<=s[x])//当队列非空的时候为了维护一个单调递减的前缀和区间队列,进行队列的更新--rear;q[++rear]=x;//将x插入到队尾++x;//并且将x的长度加一}if(q[front]<i+l-1)//当这时候队首对应的前缀和区间长度不足l的时候,将队首出队++front;ans=max(ans,s[q[front]]-s[i-1]);//更新最大的ans}cout<<ans<<endl;return 0; 
}

这一道题目需要仔细的理解单调队列在其中的运用,请读者仔细领悟与思考。

接下来看最后一道题目,覆盖:

接下来请看代码:

#include <bits/stdc++.h>using namespace std;int n, h, a[200001], q1[200001], front1 = 1, rear1 = 0, q2[200001], front2 = 1, rear2 = 0; int main() {scanf("%d%d", &n, &h);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);int j = 0, ans = 0;for (int i = 1; i <= n; i++) {if (front1 <= rear1 && q1[front1] < i)++front1;if (front2 <= rear2 && q2[front2] < i)++front2;while (j <= n && (j <= i || a[q1[front1]] - a[q2[front2]] <= h)) {++j;if (j > n)break;while (front1 <= rear1 && a[q1[rear1]] <= a[j])--rear1;q1[++rear1] = j;while (front2 <= rear2 && a[q2[rear2]] >= a[j])--rear2;q2[++rear2] = j;}ans = max(ans, j - i);}printf("%d\n", ans);
}

  1. 数组初始化

    • a[200001]:存储输入的 n 个数字。
  2. 两个单调队列

    • q1:维护最大值的单调递减队列。
    • q2:维护最小值的单调递增队列。
    • front1rear1front2rear2:队列的头尾指针。
  3. 主要逻辑

    • 通过双指针 ij 遍历数组。
    • 对于每个位置 i,在内循环中找到满足条件的 j,使得子序列中最大值和最小值的差值不超过 h
    • j 的移动过程中,更新两个单调队列 q1q2
    • 计算并更新最大长度 ans
  4. 内循环

    • j 的循环中,不断尝试扩展子序列的右边界 j,直到满足条件:a[q1[front1]] - a[q2[front2]] <= h 或者超出数组范围。
    • 更新两个队列 q1q2 以维护最大值和最小值的索引。
  5. 最终结果

    • 输出得到的最大长度 ans,即符合条件的连续子序列的最大长度。

这段代码使用了两个单调队列来记录最大值和最小值的索引,在滑动窗口的过程中寻找满足条件的子序列,并记录其长度。

感谢观看!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/235113.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Javaweb之SpringBootWeb案例的详细解析

SpringBootWeb案例 前面我们已经讲解了Web前端开发的基础知识&#xff0c;也讲解了Web后端开发的基础(HTTP协议、请求响应)&#xff0c;并且也讲解了数据库MySQL&#xff0c;以及通过Mybatis框架如何来完成数据库的基本操作。 那接下来&#xff0c;我们就通过一个案例&#xf…

生信 R语言

11.芯片表达矩阵下游分析 ​rm(list ls())#清除所有变量 options(stringsAsFactors F) #BiocManager::install("CLL") suppressPackageStartupMessages(library(CLL)) data("sCLLex") sCLLex ## ExpressionSet (storageMode: lockedEnvironment) ## as…

centos下系统全局检测工具dstat使用

目录 一&#xff1a;没有需要安装 二&#xff1a;dstat命令参数 三、监测界面各参数含义&#xff08;部分&#xff09; 四、dstat的高级用法 一&#xff1a;没有需要安装 yum install dstat 二&#xff1a;dstat命令参数 有默认选项&#xff0c;执行dstat命令不加任何参数…

2023年全国职业院校技能大赛(高职组)“云计算应用”赛项赛卷②

2023年全国职业院校技能大赛&#xff08;高职组&#xff09; “云计算应用”赛项赛卷2 目录 需要竞赛软件包环境以及备赛资源可私信博主&#xff01;&#xff01;&#xff01; 2023年全国职业院校技能大赛&#xff08;高职组&#xff09; “云计算应用”赛项赛卷2 模块一 …

Java中什么序列化?

在Java中&#xff0c;序列化是一种将对象转换为字节序列的机制&#xff0c;使得对象可以在网络上传输或存储到文件中&#xff0c;而后可以通过反序列化还原为对象。Java提供了java.io.Serializable接口&#xff0c;通过实现这个接口的类可以实现对象的序列化和反序列化。 序列…

HTTP 代理原理及实现(二)

在上篇《HTTP 代理原理及实现&#xff08;一&#xff09;》里&#xff0c;我介绍了 HTTP 代理的两种形式&#xff0c;并用 Node.js 实现了一个可用的普通 / 隧道代理。普通代理可以用来承载 HTTP 流量&#xff1b;隧道代理可以用来承载任何 TCP 流量&#xff0c;包括 HTTP 和 H…

加工零件的题解

目录 原题描述&#xff1a; 题目描述 输入格式 输出格式 样例 #1 样例输入 #1 样例输出 #1 样例 #2 样例输入 #2 样例输出 #2 提示 题目大意&#xff1a; 主要思路&#xff1a; 但是我们怎么才能判断出x走到1时L是偶数还是奇数呢&#xff1f; 初始化&#xff1a;…

UML期末复习(带习题,选择题,判断题)(持续更新)

UML期末复习 UML简介UML模型图的构成UML事物UML包含4种事物&#xff1a;构件事物&#xff1a; UML模型的静态部分&#xff0c;描述概念或物理元素行为事物&#xff1a;UML模型图的动态部分&#xff0c;描述跨越空间和时间的行为分组事物&#xff1a; UML模型图的组织部分&#…

24/1/10 qt work

1. 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密码不匹配&…

麻雀搜索算法SSA预告

麻雀搜索算法&#xff08;Sparrow Search Algorithm&#xff0c;SSA&#xff09;是一种模拟麻雀觅食行为的优化算法&#xff0c;由Ahmed K. Attiya在2018年提出。该算法通过模拟麻雀在觅食时的群体协作行为&#xff0c;以解决优化问题。 以下是麻雀搜索算法的基本原理&#xf…

Qt QCheckBox复选按钮控件

文章目录 1 属性和方法1.1 文本1.2 三态1.3 自动排他1.4 信号和槽 2 实例2.1 布局2.2 代码实现 Qt中的复选按钮类是QCheckBox它和单选按钮很相似&#xff0c;单选按钮常用在“多选一”的场景&#xff0c;而复选按钮常用在"多选多"的场景比如喜欢的水果选项中&#xf…

【C++期末编程题题库】代码+详解18道

适合期末复习c看&#xff0c;或者刚入门c的小白看&#xff0c;有的题会补充知识点&#xff0c;期末复习题的代码一般比较简单&#xff0c;所以语法上没那么严谨。本文所有题目要求全在代码块的最上面。 目录 1、设计复数类 2、设计Computer类 3、实现相加的函数模板 4、圆类…

three.js实现电子围栏效果(纹理贴图)

three.js实现电子围栏效果&#xff08;纹理贴图&#xff09; 实现步骤 围栏的坐标坐标转换为几何体顶点&#xff0c;uv顶点坐标加载贴图&#xff0c;移动 图例 代码 <template><div class"app"><div ref"canvesRef" class"canvas-…

开关电源PFC电路原理详解及matlab仿真

PFC全称“Power Factor Correction”&#xff0c;意为“功率因数校正”。PFC电路即能对功率因数进行校正&#xff0c;或者说能提高功率因数的电路。是开关电源中很常见的电路。 在电学中&#xff0c;功率因数PF指有功功率P&#xff08;单位w&#xff09;与视在功率S&#xff08…

websocket介绍并模拟股票数据推流

Websockt概念 Websockt是一种网络通信协议&#xff0c;允许客户端和服务器双向通信。最大的特点就是允许服务器主动推送数据给客户端&#xff0c;比如股票数据在客户端实时更新&#xff0c;就能利用websocket。 Websockt和http协议一样&#xff0c;并不是设置在linux内核中&a…

【昕宝爸爸定制】如何将集合变成线程安全的?

如何将集合变成线程安全的? ✅典型解析&#x1f7e2;拓展知识仓☑️Java中都有哪些线程安全的集合&#xff1f;&#x1f7e0;线程安全集合类的优缺点是什么&#x1f7e1;如何选择合适的线程安全集合类☑️如何解决线程安全集合类并发冲突问题✔️乐观锁实现方式 (具体步骤)。✅…

Kubernetes实战(十五)-Pod垂直自动伸缩VPA实战

1 介绍 VPA 全称 Vertical Pod Autoscaler&#xff0c;即垂直 Pod 自动扩缩容&#xff0c;它根据容器资源使用率自动设置 CPU 和 内存 的requests&#xff0c;从而允许在节点上进行适当的调度&#xff0c;以便为每个 Pod 提供适当的资源。 它既可以缩小过度请求资源的容器&…

Oracle regexp_substr

select regexp_substr(123|456|789, [^|], 1, 2) from dual;

C练习——N个水手分椰子

题目&#xff1a; 五个水手在岛上发现一堆椰子&#xff0c;先由第1个水手把椰子分为等量的5堆&#xff0c;还剩下1个给了猴子&#xff0c;自己藏起1堆。然后&#xff0c;第2个水手把剩下的4堆混合后重新分为等量的5堆&#xff0c;还剩下1个给了猴子&#xff0c;自己藏起1堆。以…

uniapp 解决安卓App使用uni.requestPayment实现沙箱环境支付宝支付报错

背景&#xff1a;uniapp与Java实现的安卓端app支付宝支付&#xff0c;本想先在沙箱测试环境测支付&#xff0c;但一直提示“商家订单参数异常&#xff0c;请重新发起付款。”&#xff0c;接着报错信息就是&#xff1a;{ "errMsg": "requestPayment:fail [pa…