单调栈
2022/7/14 6:20:11
本文主要是介绍单调栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
单调栈
ACWing 803
给定一个长度为 NN 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1−1。
输入格式
第一行包含整数 NN,表示数列长度。
第二行包含 NN 个整数,表示整数数列。
输出格式
共一行,包含 NN 个整数,其中第 ii 个数表示第 ii 个数的左边第一个比它小的数,如果不存在则输出 −1−1。
数据范围
1≤N≤1051≤N≤105
1≤数列中元素≤1091≤数列中元素≤109
输入样例:
5 3 4 2 7 5
输出样例:
-1 3 -1 2 2
分析
这道题题意很简单,就是为一个元素忘左走最先碰到的比他小的元素。最直观的方式就是用双重循环
/** * 栈 */ #include<bits/stdc++.h> using namespace std; const int N = 100100; int a[N]; int b[N]; int main(){ int n; cin>>n; for(int i =1; i<=n; i++) { cin>>a[i]; } for(int i = 1; i<=n; i++) { for(int j = i-1;j>=1; j--) { if(a[j]<a[i]){ b[i] = a[j]; break; } } } for(int i =1; i<=n; i++){ if(b[i]== 0){ cout<<"-1 "; }else { cout<<b[i]<<" "; } } }
但是这种方法的时间复杂度太大了O(n^2)
怎么优化呢,观察规律,如果一个数他比他的前一个数小,那么再往前搜的时候,是不是他前一个数就不会再出现了,所以我们用到单调栈
所谓单调找就是栈里的元素是有序的,那这道题怎么做呢:
当遍历到ai的时候,那它和栈顶元素比,如果比栈顶元素小,就一直出栈,知道遇到比他小的,然后将其入栈.
代码
/** * 栈 */ #include<bits/stdc++.h> using namespace std; const int N = 10010; int sta[N]; int t; int n; int main() { cin>>n; for(int i = 0; i<n; i++) { int a; cin>>a; while(t && sta[t]>=a)t--; if(t)cout<<sta[t]<<" "; else cout<<-1<<" "; sta[++t] = a; } return 0; }
这篇关于单调栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解