题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1255
———————————————————————————————————————————— 1255 字典序最小的子序列 题目来源： 天津大学OJ 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注 给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：
1、包含字符串中所有出现过的字符各1个。 2、是所有满足条件1的串中，字典序最小的。
例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。 Input 输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。 Output 输出包含S中所有出现过的字符，每个字符各1个，并且字典序最小的S的子序列。 Input示例 babbdcc Output示例 abdc
————————————————————————————————————————————————
解题思路： 我们贪心做这道题
既然他让我们找包含所有出现过的字符的字典序最小的子串，
那么对于左右出现过的字符是很好判定的，没出现过 就加进去就好了
问题是怎么找字典序最小的，
我们可以维护一个待定的子串， 首先将没有出现过的字符加进去 但加进去的同时呢，判断下待定子串的尾字符和当前待加进去的字符那个大， 如果尾字符大，并且这个尾字符在后面还有出现，我们就把尾字符删除， 这样维护下来，我们得到的一定是字典序最小的
复杂度是 O(n) 的
附本题代码 ——————————————————————————————————————————————
#include <bits/stdc++.h> using namespace std; /**********************************/ int vis[30],h[30]; char mystack[100000+7]; char str[100000+7]; int len=0; int main(){ scanf("%s",str); int sz = strlen(str); for(int i=0;i<sz;i++) h[str[i]-'a']++; for(int i=0;i<sz;i++){ h[str[i]-'a']--; if(!vis[str[i]-'a']){ while(len){ if(!h[mystack[len]-'a'] || mystack[len]<str[i]) break; vis[mystack[len]-'a']=0;len--; } vis[str[i]-'a']=1; mystack[++len]=str[i]; } } for(int i=1;i<=len;i++)printf("%c",mystack[i]);puts(""); return 0; }