CSL 的字符串
题解:
从前往后扫一遍 如果当前这个字符本身就是到当前为止第一次出现的,那肯定要留下它吧,就把它放到ans数组里面,并且把这个字母的个数减一(最开始统计的每个字母出现的个数相当于每个字母的剩余个数)然后从这个字母开始遍历ans数组中该字母前面的所有字母 ,如果前面的字母的字典序大于该字母并且该字母还有剩余的话,就把那个字母从ans数组中移出去。
注意这句话 while(cnt>0&&ans[cnt-1]>s[i]&&num[ans[cnt-1]]) 一定是从该字母的前一个开始,而不是只要存在就行,因为ans数组中的字母到当前为止一定是最优解了 。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=1e5+10;
7 char s[maxn];
8 int vis[200];//用来看看字符串中每一个字母是否曾经出现过
9 int num[200];
10 char ans[maxn];
11 int main()
12 {
13 scanf("%s",s);
14 int len=strlen(s);
15 for(int i=0;i<len;i++)
16 num[s[i]]++;//num数组是统计字符串中每一个字符出现的次数(即该字符的剩余可替换次数)
17 int cnt=0;
18 for(int i=0;i<len;i++)
19 {
20 num[s[i]]--;
21 if(vis[s[i]])//如果s[i]在前面出现了 那么直接跳过
22 continue;
23 //如果s[i]是第一次出现,那么对于当前来说 一定要把它放到ans数组中
24 //while循环的作用是:从ans数组的最后一个字符开始往前遍历,如果该字符比s[i]字典序大,而且剩余可替换次数
25 //不为0,那么说明该字符在后面还出现过,那么把它放到后面会比它在现在的位置使得整个ans字典序更小
26 //所以我们就把该字符之前的标记清零,把它从ans中移走(即cnt--)
27 while(cnt>0&&ans[cnt-1]>s[i]&&num[ans[cnt-1]])
28 {
29
30 vis[ans[cnt-1]]=0;
31 cnt--;
32 }
33 vis[s[i]]=1;
34 ans[cnt++]=s[i];
35 }
36 for(int i=0;i<cnt;i++)
37 {
38 printf("%c",ans[i]);
39 }
40 return 0;
41 }