P1165 日志分析

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=200010;
//mxstk和stk始终保持相同的大小，记录的是从栈底到该位置的最大值，弹出的话不会将所有的最大值弹出，如果最后一个加入的不是最大值的话那么前面的数依旧是最大值
int stk[N],mxstk[N];
int n,tt;int main()
{cin>>n;int op,x;while(n--){cin>>op;if(op==0){cin>>x;stk[++tt]=x;if(tt==0) mxstk[tt]=x;else mxstk[tt]=max(x,mxstk[tt-1]);}else if(op==1){tt--;}else if(op==2){if(tt==0) cout<<0<<endl;else cout<<mxstk[tt]<<endl;}}return 0;
}

核心是辅助栈的构建，辅助栈应当保持和主栈一样的大小并且记录从栈底到tt的最大值如main 2 3 5 2 6max2 3 5 5 6