【AcWing】830. 单调栈
AcWing 单调
2023-09-14 09:15:03 时间
830. 单调栈
给定一个长度为 N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
输入格式
第一行包含整数 N,表示数列长度。
第二行包含 N个整数,表示整数数列。
输出格式
共一行,包含 N个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
思路:
用单调递增栈,当该元素可以入栈时(即该元素比栈顶元素大时),栈顶元素就是它左侧第一个比他小的元素。
代码样例:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int stk[N],tt;
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
scanf("%d",&x);
while(tt&&stk[tt]>=x) tt--;//如果栈顶元素比 当前待入栈元素大,则出栈
if(!tt) printf("-1 ");//如果栈空,则没有比该元素小的值
else printf("%d ",stk[tt]);//栈顶元素就是左侧第一个比他小的元素
stk[++tt]=x;
}
return 0;
}
相关文章
- AcWing 21. 斐波那契数列
- AcWing 电话列表
- AcWing算法学习---dfs
- AcWing算法学习第三节---高精度问题.
- AcWing算法学习之二分法
- Acwing——第 89 场周赛
- Acwing——第88场周赛
- Acwing——第 87 场周赛
- Acwing——第86场周赛
- Acwing——第二场热身赛
- Acwing——第80场周赛
- Acwing——第79场周赛
- 【AcWing】829. 模拟队列
- 【AcWing】 3302. 表达式求值
- 【AcWing】828. 模拟栈
- 【AcWing】827. 双链表
- 【AcWing】 826. 单链表
- 【AcWing】790. 数的三次方根
- 【AcWing】789. 数的范围
- 【AcWing】 788. 逆序对的数量
- 【AcWing】787. 归并排序
- 【AcWing】786. 第k个数
- 【AcWing】 785. 快速排序
- 【AcWing算法基础】学习笔记01——快速排序、归并排序、二分