链接：https://ac.nowcoder.com/acm/contest/551/D来源：牛客网题目描述
CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。 给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件： 原字符串中出现的字符，新字符串也必须包含。 新字符串中所有的字符均不相同。 新字符串的字典序是满足上面两个条件的最小的字符串。 输入描述: 仅一行，有一个只含有可打印字符的字符串 s。 |s|≤1e5 输出描述: 在一行输出字典序最小的新字符串。 示例1 输入 bab输出 ab 示例2 输入 baca输出 bac备注: ASCII字符集包含 94 个可打印字符(0x21 - 0x7E)，不包含空格。题解：使用栈进行模拟，如果当前字符已经在栈中，则跳过(保证了每个字符只存一次)，否则进行如下操作：如果当前字符比栈顶元素小并且栈顶元素在之后的序列中仍有剩余，就弹出栈顶元素，持续这个过程直到栈顶元素比当前元素小或者栈顶元素没有剩余，然后把当前字符放入栈中(保证了所有字符都会存入栈中) 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstdio> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 typedef long long ll; 10 const ll mod= 998244353; 11 char cc[100005],ch[100005]; 12 int in[10005]; 13 bool vis[10005]; 14 int main(){ 15 scanf("%s",ch); 16 int len=strlen(ch); 17 for(int i=0;i<len;i++){ 18 in[ch[i]]++; 19 } 20 int tot=0; 21 for(int i=0;i<len;i++){ 22 in[ch[i]]--; 23 if(!vis[ch[i]]){ 24 vis[ch[i]]=1; 25 while(tot&&cc[tot]>ch[i]&&in[cc[tot]]){ 26 vis[cc[tot]]=0; 27 tot--; 28 } 29 cc[++tot]=ch[i]; 30 } 31 } 32 for(int i=1;i<=tot;i++){ 33 printf("%c",cc[i]); 34 } 35 printf("\n"); 36 return 0; 37 } View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/10633080.html
相关资源：各显卡算力对照表！