题干：
CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。
给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：
- 原字符串中出现的字符，新字符串也必须包含。
- 新字符串中所有的字符均不相同。
- 新字符串的字典序是满足上面两个条件的最小的字符串。
输入描述:
仅一行，有一个只含有可打印字符的字符串 s。
|s|≤105|s|≤105
输出描述:
在一行输出字典序最小的新字符串。 示例1
输入
bab 输出
ab 示例2
输入
baca 输出
bac 备注:
ASCII字符集包含 94 个可打印字符(0x21 - 0x7E)，不包含空格。 解题报告：
这题是类似单调栈的思想，只不过弹出的时候要判断一下是否后面还有改数字。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 1e5 + 5;
string s;
bool vis[MAX];
int bk[555],tot;
stack<char > sk;
int main() {
cin>>s;
int len = s.size();
s = ' ' + s;
for(int i = 1; i<=len; i++) {
bk[s[i]]++;
}
string ans;
int cur = 1,pos = 1;
for(int i = 1; i<=len; i++) {
char tar = s[i];
bk[tar]--;
if(vis[tar]) continue;
while( sk.size() && bk[sk.top()] && tar < sk.top()) {
vis[sk.top()] = 0;
sk.pop();
ans.pop_back();
}
ans += tar;
sk.push(tar);
vis[tar] = 1;
}
cout << ans << endl;
return 0 ;
}
//bcdddbca
京公网安备 11010502036488号