字典之序

题目描述
众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没
什么关系。
小葱同学最近醉心于字典序的研究,他苦学百年,已经牢牢掌握怎么比较两个字符串的字典序谁大谁小。这天小葱外出摸鱼的时候在路上发现了一个字符串s,但这个字符串里面有很多重复的字符。现在小葱希望让出现过的字符都保留恰好一个,使得剩下的字符串字典序最小。

输入
一行一个字符串
输出
一行一个字符串代表答案。

样例输入
cbabc
样例输出
abc

题解:
先统计每个字符出现的次数,然后用单调栈维护一个从小到大的字典序,判断每个字符,如果当前在栈里面已有那个字符就跳过,如果没有则和栈首元素比较,当前字母小于栈首并且栈首元素的个数大于0(保证了每个字符至少有一个),就把栈首出栈,最后再把合适的字母放入。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char st[maxn];
int cnt[26] = {0};
char s[maxn];
bool vis[30];

int main()
{
  int p = -1;
  scanf("%s",s);
  int len = strlen(s);
  for(int i = 0; i < len; i ++)
    cnt[s[i] - 'a'] ++;
  for(int i = 0; i < len; i ++){
    cnt[s[i] - 'a'] --;
    if(vis[s[i] - 'a'])
      continue;
    while(p > -1 && cnt[st[p] - 'a'] > 0 && st[p] > s[i]){
      vis[st[p] - 'a'] = false;
      p --;
    }
    vis[s[i] - 'a'] = true;
    st[++ p] = s[i];
  }
  cout << st << endl;
  return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注