算法学习Day1——【数据结构】单调栈

ops/2025/2/12 15:30:31/

1.什么是单调栈以及单调栈的作用

(1)定义

顾名思义,单调栈是一个有序的栈,可能从栈顶到栈底单调递增(单调递增栈),也有可能从栈顶到栈底单调递减(单调递减栈)

(2)用途

单调栈可以在时间复杂度为 O(n)$的情况下,求解出某个元素左边或者右边第一个比它大或者小的元素。

所以单调栈一般用于解决一下几种问题:

1.寻找左侧第一个比当前元素大的元素。

2.寻找左侧第一个比当前元素小的元素。

3.寻找右侧第一个比当前元素大的元素。

4.寻找右侧第一个比当前元素小的元素。

那么我们在这里进行对上述四种问题进行阐述,

1.寻找左侧第一个比当前元素大的元素,我们可以创建一个单调递增栈,把我们这个元素与栈顶元素进行比较,如果栈顶元素小于要该元素,那么直接将栈顶元素弹出,然后继续比较,直到找到第一个比这个元素大的元素,或者说栈为空,如果栈为空,那么说明左边不存在比这个元素更大的元素了

2.寻找左侧第一个比当前元素小的元素,我们创建一个单调递减栈,将这个栈顶元素和该元素进行比较,如果该项元素大于栈顶元素,那么就要将该元素插入,并且此时的栈顶元素就是左侧第一个比该元素小的元素

3.寻找右侧第一个比当前元素大的元素,我们创建一个单调递增栈,然后从左向右遍历,第一个将这个元素从栈中弹出的元素就是右侧第一个比这个元素大的

4.寻找右侧第一个比当前元素小的元素,我们要创建单调递减栈,然后从左向右遍历,就是第一个将该元素从栈中弹出的就是右侧第一个比这个元素小的

(3)伪代码

stack<int> st;
//此处一般需要给数组最后添加结束标志符,具体下面例题会有详细讲解
for (遍历这个数组)
{if (栈空 || 栈顶元素大于等于当前比较元素){入栈;}else{while (栈不为空 && 栈顶元素小于当前元素){栈顶元素出栈;更新结果;}当前数据入栈;}
}

2.相关例题

1.模版单调栈 

纯模版题,没啥可说的,记得往栈里面存的是结构体就行 

#include<bits/stdc++.h>
using namespace std;
int n;int f[3000005];
struct node
{int w;int flag;
}a[3000005];
stack<node> q;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].w;a[i].flag=i;}for(int i=1;i<=n;i++){while(!q.empty()&&a[q.top().flag].w<a[i].w){f[q.top().flag]=i;q.pop();}q.push(a[i]);}for(int i=1;i<=n;i++){printf("%d ",f[i]);}
}

 2.Look Up S

和上面的题一个板子

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{int h;int flag;
}a[100005];
int f[100005];
stack<node> q;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].h;a[i].flag=i;}for(int i=1;i<=n;i++){while(!q.empty()&&q.top().h<a[i].h){f[q.top().flag]=i;q.pop();}q.push(a[i]);}for(int i=1;i<=n;i++){printf("%d\n",f[i]);}
}

3. 求数列所有后缀最大值的位置

 

这题两个知识点,一个是异或操作,另一个是单调栈

#include<bits/stdc++.h>
using namespace std;struct node{unsigned long long w;int flag;
}a[1000005];
int n;
long long sum;
stack<node> q;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].w;a[i].flag=i;}for(int i=1;i<=n;i++){while(!q.empty()&&q.top().w<a[i].w){sum^=q.top().flag;q.pop();}q.push(a[i]);sum^=q.top().flag;printf("%lld\n",sum);}return 0;
} 

 


http://www.ppmy.cn/ops/30306.html

相关文章

Linux的Shell脚本详解

本文目录 一、什么是 Shell 脚本文件 &#xff1f;二、编写Shell脚本1. 基本规则2. shell 变量&#xff08;1&#xff09;创建变量&#xff08;2&#xff09;引用变量&#xff08;3&#xff09;删除变量&#xff08;4&#xff09;从键盘读取变量&#xff08;5&#xff09;特殊变…

JavaEE技术之MySql高级(索引、索引优化、sql实战、View视图、Mysql日志和锁、多版本并发控制)

文章目录 1. MySQL简介2. MySQL安装2.1 MySQL8新特性2.2 安装MySQL2.2.1 在docker中创建并启动MySQL容器&#xff1a;2.2.2 修改mysql密码2.2.3 重启mysql容器2.2.4 常见问题解决 2.3 字符集问题2.4 远程访问MySQL(用户与权限管理)2.4.0 远程连接问题1、防火墙2、账号不支持远程…

【会员单位】浙江晧月水务科技有限公司

中华环保联合会理事单位 水环境治理专业委员会副主任委员单位 公司成立于2018年3月14日&#xff0c;是专业研究废水处理业务的国家高新技术企业。 公司自主研发的脱硫废水“零排放”的技术&#xff0c;不仅适应性好&#xff0c;技术先进&#xff0c;智慧化程度高&#xff0c…

Python语言零基础入门——文件

目录 一、文件的基本概念 1.文件 2.绝对路径与相对路径 3.打开文件的模式 二、文件的读取 三、文件的追加 四、文件的写入 五、with语句 六、csv文件 1.csv文件的读取 2.csv文件的写入 七、练习题&#xff1a;实现日记本 一、文件的基本概念 1.文件 文件是以计算…

【Stable Diffusion本地部署简易教程】从入门到实践

Stable Diffusion 本地部署指南&#xff1a;简单易懂的图文教程 引言 Stable Diffusion是一种深度学习模型&#xff0c;用于生成高质量的图像。本地部署意味着你可以在自己的计算机上运行这个模型&#xff0c;从而无需依赖于在线服务。本教程将循序渐进地指导你如何在自己的计…

Java实现裁剪PDF

目录 安装Java PDF库 Java裁剪PDF页面 Java裁剪PDF页面并将结果保存为图片、HTML、Excel等格式 裁剪PDF页面是一项常见的任务&#xff0c;它可以用来调整文档的尺寸和去除不需要的边距或白边。通过裁剪页面&#xff0c;你可以优化文档的布局和展示效果&#xff0c;使其更符合…

idm下载速度慢解决办法 idm批量下载怎么用 idm优化下载速度 Internet Download Manager解决下载速度慢的方法教程

IDM (Internet Download Manager)是一款兼容性大&#xff0c;支持多种语言的下载管理软件&#xff0c;它可以自动检测并下载网页上的内容&#xff0c;这正是这一优点&#xff0c;使得它受到了广大用户的喜爱。但是在下载的过程中&#xff0c;我们会遇到idm下载速度慢怎么回事&a…

无人机+三维建模:倾斜摄影技术详解

无人机倾斜摄影测量技术是一项高新技术&#xff0c;近年来在国际摄影测量领域得到了快速发展。这种技术通过从一个垂直和四个倾斜的五个不同视角同步采集影像&#xff0c;从而获取到丰富的建筑物顶面及侧视的高分辨率纹理。这种技术不仅能够真实地反映地物情况&#xff0c;还能…