我是手打栈,没用STL
by xukaiyi_kaiyi @ 2021-07-31 13:39:31
你要先判断空栈,再访问栈顶,否则应该还是访问空栈
by xukaiyi_kaiyi @ 2021-07-31 13:45:36
21行是或的关系
by xukaiyi_kaiyi @ 2021-07-31 13:48:44
```cpp
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
stack<int>a;
int ans[3000005],a1[3000005];
int cnt;
int main(){
memset(ans,0,sizeof(ans));
int n;
cin>>n;
for(int i=1 ; i<=n ; i++){
cin>>a1[i];
cnt++;
if(a.empty()) a.push(a1[i]);
else{
if(a.top()<a1[i]){
while(!a.empty()){//只用判断是否为空
if(a.top()<a1[i]){//那么这里就不用判断是否为空了,也就不拍访问空栈了
ans[a.top()]=cnt;
a.pop();
}
else{//这里直接用else就可以了
a.push(a1[i]);
break;
}
if(a.empty()){
a.push(a1[i]);
break;
}
}
}else a.push(a1[i]);
}
}
for(int i=1 ; i<=n ; i++) cout<<ans[a1[i]]<<" ";
return 0;
}
```
by xukaiyi_kaiyi @ 2021-07-31 13:53:06
但应该还是有问题
by xukaiyi_kaiyi @ 2021-07-31 13:54:37
你的思路到底是啥?
应该是倒序入栈,栈是单调不增的,栈顶元素的下标就是那个数右边第一个比它大的数。
我用STL给你写一份吧
by xukaiyi_kaiyi @ 2021-07-31 14:10:06
[是我算法有问题吗?](https://www.luogu.com.cn/record/54630381)
STL的问题吗?
4个TLE
by xukaiyi_kaiyi @ 2021-07-31 14:46:32
```cpp
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int MAXN=3e6+5;
struct node{
int data;
int order;
};
stack<node>a;
int sav[MAXN];
int ans[MAXN];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>sav[i];
}
for(int i=n;i>=1;i--){
if(!a.empty()){
while(!a.empty()){
if(a.top().data<=sav[i]){
a.pop();
}
else{
ans[i]=a.top().order;
a.push((node){sav[i],i});
break;
}
}
if(a.empty()){
ans[i]=0;
a.push((node){sav[i],i});
}
}
else{
ans[i]=0;
a.push((node){sav[i],i});
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
return 0;
}
```
[吸完氧气(O2)竟然AC了](https://www.luogu.com.cn/record/54630665)
by xukaiyi_kaiyi @ 2021-07-31 14:51:10
[scanf就能AC](https://www.luogu.com.cn/record/54631253)
STL要scanf,手打栈cin就行
cin 1.20s超时
scanf 就638ms
这告诉我们了什么?
@[yangyuanxi44](/user/450893)
by xukaiyi_kaiyi @ 2021-07-31 15:00:36
@[xukaiyi_kaiyi](/user/403779) ok 谢谢kaiyi
by yangyuanxi44 @ 2021-07-31 16:41:27