题目链接:https://ac.nowcoder.com/acm/contest/551/D
题目大意:
题目描述
CSL 以前不会字符串算法,经过一年的训练,他还是不会……于是他打算向你求助。
给定一个字符串,只含有可打印字符,通过删除若干字符得到新字符串,新字符串必须满足两个条件:
- 原字符串中出现的字符,新字符串也必须包含。
- 新字符串中所有的字符均不相同。
- 新字符串的字典序是满足上面两个条件的最小的字符串。
输入描述:
仅一行,有一个只含有可打印字符的字符串 s。 |s|≤105|s|≤105
输出描述:
在一行输出字典序最小的新字符串。
CSL的字符串
具体思路:
对于每一个字符,我们保存它存在的最后位置,然后用单调栈维护一个单调递增的序列就可以了。如果当前的字符大于栈顶的字符,并且当前栈顶字符的最大位置大于当前的i,就先将这个字符弹出。
AC代码:
#include<bits/stdc++.h>
using namespace std;
# define ll long long
const int maxn =2e5+;
char str[maxn];
map<char,int>pos;
map<char,int>vis;
int main()
{
stack<char>q;
scanf("%s",str+);
int len=strlen(str+);
for(int i=; i<=len; i++)
{
pos[str[i]]=i;
}
for(int i=; i<=len; i++){
if(vis[str[i]])continue;
while(!q.empty()&&q.top()>str[i]&&pos[q.top()]>i){
vis[q.top()]=;
q.pop();
}
q.push(str[i]);
vis[str[i]]=i;
}
string ans;
while(!q.empty()){
ans+=q.top();
q.pop();
}
reverse(ans.begin(),ans.end());
cout<<ans<<endl;
return ;
}