316. Remove Duplicate Letters (贪心)

你的名字 2024-04-19 00:41 70阅读 0赞

题目描述：

说是要删除重复的字母，系统只会给小写字母，然后所选的删除策略会使字典序较小的字母尽可能排在前面，比如'a'排在'b'前面。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

思路：

首先一个大体策略：先把当前字符前面的那些字符进行判断，如果当前字符字典序 < 前面字符的字典序，那么如果前面字符在当前字符的后面也出现了，那么可以删除前面的字符。

我们这里用一种数据结构会比较好处理——栈

具体思路：

*  先用一个int数组记录每个字母出现次数（下标用字母和a字母的差值）（节省判断重复字符的时间）
 *  第一个元素直接入栈初始化
 *  遍历到的元素和栈顶元素作对比，若遍历到的元素 > 栈顶元素 && 栈中没有和遍历到的元素相同元素：遍历到的元素入栈
 *  遍历到的元素和栈顶元素作对比，若遍历到的元素 < 栈顶元素：判断是否后面有重复的元素，有的话删除栈顶，继续往前判断，知道栈中出现比当前元素大的元素或栈中元素在后面没有重复时将当前元素入栈
 *  注意点：遍历过的元素要将其对应的字母出现次数 - 1、用过的字母记录下来

代码：

class Solution {
    public:
        string removeDuplicateLetters(string s) {
            //栈逐个存储
            //"bcabc"
            //[ b ]
            //[ b c ]
            //[ b ]
            //[ a ]
            //出现字典序更小的字符，判断前面的字符有没有在后面出现，出现的话出栈
            stack<char> strStack;
            //记录字母都出现多少次就不用再去扫描了
            int letter[50];
            //记录用到了那些字母
            int useLetter[50];
            memset(letter, 0, sizeof(letter));
            memset(useLetter, 0, sizeof(useLetter));
            //字符串长度
            int strLen = s.length();
            if(strLen == 0) return "";
            //记录字母出现次数
            for(int i = 0; i < strLen; i++){
                letter[s[i] - 'a'] += 1;
            }
            //第一个元素无论如何都要入
            strStack.push(s[0]);
            useLetter[s[0] - 'a'] += 1;
            letter[s[0] - 'a'] -= 1;
            for(int i = 1; i < strLen; i++){
                letter[s[i] - 'a'] -= 1;
                //判断前面有没有用过
                if(useLetter[s[i] - 'a'] <= 0) {
                    //栈顶就是前面一个
                    //如果字典序比前面小的话要考虑前面的需不需要删掉，如果大的话直接加嘛，前面部分已经考虑好了
                    if(s[i]-'a' > strStack.top()-'a'){
                        strStack.push(s[i]);
                        useLetter[s[i] - 'a'] += 1;
                    }else if(s[i] - 'a' < strStack.top() - 'a'){
                        while(!strStack.empty()){
                            //往前一直扫到一定条件结束
                            if(s[i] - 'a' < strStack.top() - 'a'){
                                if(letter[strStack.top() - 'a'] > 0){
                                    // //记录哪个已经用过了
                                    useLetter[strStack.top() - 'a'] -= 1;
                                    //后面有相同的就可以pop出来
                                    strStack.pop();
                                }else{
                                    //不重复情况
                                    break;
                                }
                            }else break;
                        }
                        //记得把当前的元素塞进去
                        strStack.push(s[i]);
                        useLetter[s[i] - 'a'] += 1;
                    }
                    //等于情况不用变嘛，前面那个出来这个进去等于没操作
                }
                
            }
            vector<char> tmp;
            while(!strStack.empty()){
                tmp.push_back(strStack.top());
                strStack.pop();
            }
            string result ="";
            for(int i = tmp.size()-1; i >= 0; i--) result += tmp[i];
            return result;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

讲道理A出去的时候我都惊了出现了个0ms，测试数据长度太小了咩

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b3dd6b29119f4fe592c7bfb610c94b83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1898a9fe697448789decb535c206d50b.png