地址

https://leetcode.com/problems/remove-duplicate-letters/

题目

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

思路

（这傻逼题我想了好久没做出来，感觉自己现在就是个智障。。。

这题首先用一个cnt数组，cnt[x]表示字符x+'a'在原字符串中出现的次数。

然后用栈做，从左向右扫描字符串，每遇到一个字符c，执行以下操作：

• 栈为空时，把当前字符压入栈中，入栈时cnt[c-'a']--
• 栈不为空，且当前字符不在栈中时，把字符压入栈中，入栈时cnt[c-'a']--
• 栈不为空，且当前字符大于栈顶字符时，把当前字符压入栈，入栈时cnt[c-'a']--
• 栈不为空，且当前字符小于栈顶字符，并且栈顶字符 cnt[sk[top]]>0（即栈顶元素在会在字符串后面出现时，将栈顶元素出栈。该操作循环到条件不成立时。

代码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int len = s.length();
        int cnt[30], in[30];
        char sk[30];
        int top=-1;
        memset(cnt, 0, sizeof cnt);
        memset(in, 0, sizeof in);
        for(auto &c:s)
            cnt[c-'a']++;
        for(auto &c:s)
        {
            int p = c - 'a';
            while(~top && !in[p] && sk[top]>c && cnt[sk[top]-'a']>0)
                in[sk[top--]-'a']=0;
            if( top==-1 || (!in[p] || (!in[p] && sk[top]<c)))
                sk[++top] = c, cnt[p]--, in[p]=1;
            else if(in[p])
                cnt[p]--;
        }
        string ans;
        for(int i=0;i<=top;i++)
            ans+=sk[i];
        return ans;
    }
};