给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：
1、包含字符串中所有出现过的字符各1个。
2、是所有满足条件1的串中，字典序最小的。
例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。
输入
输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。
输出
输出包含S中所有出现过的字符，每个字符各1个，并且字典序最小的S的子序列。
输入样例
babbdcc
输出样例
abdc
题目思路：用一个栈来储存答案，从左到右遍历一遍字符串，如果在栈中（有标记）直接continue。如果串中字符小于栈顶且字符串中还有栈顶元素则出栈，且取消标记。（这里应该用while循环，有可能栈中多个元素都要出栈），没有标记的直接进栈，标记。最后倒序输出就是了。
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; char s[maxn], ans[maxn]; int cnt[maxn], vis[maxn]; stack<char> st; int main() { scanf("%s", s); int n = strlen(s); for (int i = 0; i < n; i++) { cnt[s[i]]++; //记录数量 } for (int i = 0; i < n; i++) { cnt[s[i]]--; if (vis[s[i]]) { //如果该字符已经在栈中，直接跳过 continue; } while (!st.empty() && st.top() > s[i] && cnt[st.top()] > 0) { //如果当前字符比栈顶元素要小，且当前栈顶元素可以在后面找的到，退栈（取消栈标记） vis[st.top()] = 0; st.pop(); } st.push(s[i]); vis[s[i]] = 1; } int tot = 0; while(!st.empty()) { ans[++tot] = st.top(); st.pop(); } for (int i = tot; i >= 1; i--) { printf("%c", ans[i]); } printf("\n"); return 0; }
