数据结构与算法-去除重复字符串，保持字典序最小

题目: 去除重复字母(LeetCode-困难)

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）
示例1:
输入:"bcabc"
输出:"abc"

示例2:
输入:"cbacdcbc"
输出:"acdb"

字典序:

字符串之间比较和数字比较不一样; 字符串比较是从头往后挨个字符比较,那个字符串大取决于两个字符串中第一个对应不相等的字符; 例如 任意一个a开头的字符串都大于任意一个b开头的字符串;例如字典中apple 大于 book;
题目的意思,你去除重复字母后,需要按最小的字典序返回.并且不能打乱其他字母的相对位置;
例如 bcabc 你应该返回abc, 而不是bca,cab;
例如 cbacdcbc 应该返回acdb,而不是cbad,bacd,adcb
例如 zab,应该返回zab,而不是abz;

算法思想：

1.判断字符串可能出现的特殊情况
2.用一个record数组记录字符出现次数
3.申请一个字符串栈stack来处理数据，
4.遍历字符串
5.从0~top遍历stack,判断当前字符S[i]是否在栈中存在isExist
6.如果存在，record[S[i]]--,并且继续循环遍历下一个字符（说明当前字符已经存到栈中了，不用继续存）
7.若不存在，需要找到正确的位置存储，也就是要保持栈是递减的
循环：若栈顶元素比当前字符大并且记录大于1，将栈顶元素出栈，直到不满足条件将当前字符入栈。
top > -1表示栈非空
stack[top] > s[i]表示栈顶元素比当前元素大
record[stack[top]] > 1表示后面还会出现
8.遍历完所有字符，则在stack后面添加结束符'\0'，并返回stack的首地址

char *removeDuplicateLetters(char *s) {
    //简单判断特出情况
    if (s == NULL || strlen(s) == 0) {
        return "";
    }
    if (strlen(s) == 1) {
        return s;
    }
    
    int record[26] = {0};
    int len = (int)strlen(s);
    for (int i=0; i<len; i++) {
        record[s[i]-'a']++;
    }
     //申请一个字符串stack;(用栈的特性来进行stack字符串的数据进出，并不一定非要创建一个栈)
    char *stack = (char *)malloc(sizeof(char)*(len+1));
     //memset(void *s, int ch, size_t n) 将stack len*2*sizeof(char)长度范围的空间填充0;
    memset(stack, 0, strlen(stack));
    int top = -1;
    for (int i=0; i<len; i++) {
        int isExist = 0;
        for (int j=0; j<=top; j++) {
            if (s[i] == stack[j]) {
                isExist = 1;
                break;
            }
        }
        if (isExist) {
            record[s[i]-'a']--;
        } else {
            while (top>-1 && stack[top]>s[i] && record[s[i]]>0) {
                top--;
            }
            stack[++top] = s[i];
        }
    }
    
    stack[++top] = '\0';
    
    return stack;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    char *s ;
    s = removeDuplicateLetters("cbacdcbc");
    printf("%s\n",s);
    return 0;
}