AcWing 830. 单调栈 C语言的一个奇怪算法,我也不知道怎么debug出来的
原题链接
简单
作者:
Time.Er
,
2020-11-29 23:27:58
,
所有人可见
,
阅读 724
由Y总的方法获得的灵感,但是去用C语言实现的,原谅我,大一新生刚接触编程不久,C++不熟悉,大多题都是用C去写的(在努力学习java了)
我不知道我的方法是怎么通过的,感觉晕晕的,我用temp去记录此时数组是否由一个元素存在,然后看前一个和后一个的大小进行取代栈和放入栈,方法略奇怪,在努力向Y神看齐了
#include <stdio.h>
#define N 100010
int n;
int stack[N],tt=0,temp = 0;
int main(){
scanf("%d",&n);
for(int i = 0;i < n;i++){
int x;
scanf("%d",&x);
while( x <= stack[tt] ) {
if(tt > 1) stack[tt--] = 0;
else {
stack[tt] = x;
temp = 0;
break;
}
}
if(temp == 0 ) { //3
printf("-1 ");
stack[++ tt] =x;
temp = 1;
}else if(x > stack[tt] ) {
stack[++ tt] = x;
printf("%d ",stack[-- tt]);
tt++;
}
}
return 0;
}
当然 ,y总神法
#include <stdio.h>
#define N 100010
int s[N],tt;
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
while(tt&&s[tt]>=x) tt--;
if(tt) printf("%d ",s[tt]);
else printf("-1 ");
s[++tt]=x;
}
return 0;
}