题目描述
给定一个长度为几的、仅由小写字母组成的字符串，将其按序依次放入栈中。
请问在所有可能的出栈序列中，字典序最小的出栈序列是多少?
输入格式
输入第一行，一个正整数几
输入第二行，一个长度为几的字符串
输出格式
输出所有出栈序列中，字典序最小的出栈序列
数据范围
对于 30%的数据，1<n< 10
0
。对于 60%的数据，1<n< 103
。对于100%的数据，1<n<105
样例数据
输入:
3
yes
输出:
esy
说明:
字符y、e、s依次进栈，所有出栈的可能性有：
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小
分析
知识点：贪心
解题思路：
记录 l a s i las_i lasi 为从 i 开始的后缀的最小字母，可以从后往前扫预处理
那么考虑，在字典序最小的意义下，如果栈顶的数大于后缀，就压栈，否则弹栈
复杂度 O ( n ) O(n) O(n)
把 l a s n + 1 = 30 ( > 26 ) las_{n+1}=30(>26) lasn+1=30(>26) 可以避免讨论很多细节
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int const N=1e5+10;
int n,st[N],r,las[N];
char s[N];
int main(){
scanf("%d%s",&n,s+1);
las[n+1]=30;
for(int i=n;i;i--) las[i]=min(las[i+1],s[i]-'a');
for(int i=1;i<=n;i++){
int x=s[i]-'a'; st[++r]=x;
// cout<<x<<' '<<las[i+1]<<endl;
while(r>0&&st[r]<=las[i+1]) printf("%c",st[r--]+'a');
}
}