(背思路)316. 去除重复字母(贪心)

深碍√TFBOYSˉ_ 2022-10-29 07:47 80阅读 0赞

\#\#\# 解题思路

贪心思路:遍历字符串,尝试将每个字母入栈,如果栈顶字母值大于当前要入栈的字母的值,则将栈顶的那个字母出栈

同时要保证每个元素的个数不为0

开两张哈希表用来保存每个字母出现的次数以及是否已经存在于栈中

然后遍历字符串即可

\#\#\# 代码

class Solution {
    public:
        vector<int> st;
        unordered_map<int,bool> vis;
        unordered_map<int,int> times;  //出现的次数
        string removeDuplicateLetters(string s) {
            for(int i = 0; i < s.size();++i){
                vis[s[i]-'a'] = false;    //统计是否被访问过
                times[s[i]-'a']++;   //统计每个字符出现的次数
            }
            for(int i = 0; i < s.size(); ++i){
                if(vis[s[i]-'a']){   //如果这个字母已经在栈中了,则略过
                    times[s[i]-'a']--;
                    continue;
                }
                while(!st.empty() && s[i]-'a' <= st[st.size()-1]){  //如果栈顶元素值大于当前要入栈的元素,则将那个元素出栈
                    int a = st[st.size()-1];
                    if(times[a] == 1) break;  //同时要保证被删除的那个字符个数不能为0
                    vis[a] = false;
                    times[a]--;
                    st.pop_back(); //出栈
                }
                st.push_back(s[i]-'a');
                vis[s[i]-'a'] = true;
            }
            string res;
            for(auto x:st) res.push_back(x+'a');
            return res;
        }
    };