[原创]51nod 1255 字典序最小的子序列 []【贪心】

2017-03-13 08:56:49 Tabris_ 阅读数：575

博客爬取于2020-06-14 22:41:17
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61912463

题目链接：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)O(n)的

附本题代码
——————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 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;
}