题目链接
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1255
题意
给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：
1、包含字符串中所有出现过的字符各1个。
2、是所有满足条件1的串中，字典序最小的。
例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。
题解
用栈存字符。
遍历字符串S，当前字符为c。
如果栈为空，直接将字符入栈；
如果已存在该字符，跳过；
如果栈顶元素是最后一个独苗，没有字符能让它出栈，c入栈；
如果c比栈顶元素小，那么栈顶元素出栈；
剩下情况，直接入栈。
时间复杂度O（n）。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=26;string s;
bool vis[maxn];
int cnt[maxn];
int ans[maxn];
stack<int> sta;int main()
{while(cin>>s){memset(cnt,0,sizeof(cnt));for(int i=0;i<s.size();i++)cnt[s[i]-'a']++;memset(vis,false,sizeof(vis));while(!sta.empty()) sta.pop();for(int i=0;i<s.size();i++){int c=s[i]-'a';//cout<<"c="<<c<<endl;if(sta.empty()){// cout<<"a"<<endl;cnt[c]--;sta.push(c);vis[c]=true;continue;}if(vis[c]){// cout<<"b"<<endl;cnt[c]--;continue;}if(!cnt[sta.top()]){// cout<<"c"<<endl;sta.push(c);cnt[c]--;vis[c]=true;continue;}if(c<sta.top()){// cout<<"e"<<endl;while(!sta.empty() && cnt[sta.top()] && c<sta.top()){vis[sta.top()]=false;sta.pop();}sta.push(c);cnt[c]--;vis[c]=true;continue;}sta.push(c);vis[c]=true;cnt[c]--;}int cnt=0;while(!sta.empty()){int c=sta.top();sta.pop();ans[cnt++]=c;}reverse(ans,ans+cnt);//cout<<"cnt="<<cnt<<endl;for(int i=0;i<cnt;i++){char ch='a'+ans[i];cout<<ch;}cout<<endl;}return 0;
}