AcWing 830. 单调栈
原题链接
简单
作者:
cubbyZ
,
2021-01-26 21:53:49
,
所有人可见
,
阅读 323
题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
时间复杂度 O(n)
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
C 代码
#include <stdio.h>
const int N = 100010;
int n;
int stk[N], tt;
int main()
{
scanf("%d",&n);
for(int i =0; i< n; i++)
{
int x;
scanf("%d",&x);
while( tt && stk[tt]>= x) tt--; //如果栈中有元素 且 元素大于当前元素 则删掉
if(tt) printf("%d ",stk[tt]); //若栈中有元素,则输出 比当前小且最近的值
else printf("-1 "); //若没有元素,则输出 -1
stk[++ tt] = x; //元素入栈
}
return 0;
}
blablabla