LeetCode316-去除重复字母-栈-贪心-字符串

原题链接

Note：

维护一个答案字符串，遍历给的字符串，每次判断一下当前这个字符，是不是比答案字符串的末尾小，如果小的话，那就看看这个末尾的能不能删，能删就删掉，不能删那没办法，就继续放着

代码如下：

class Solution {
    
public:
    string removeDuplicateLetters(string s) {
    
        string stk;
        unordered_map<char, bool> ins;
        unordered_map<char, int> last;
        for(int i = 0; i < s.size(); i ++)  last[s[i]] = i;

        for(int i = 0; i < s.size(); i ++){
    
            if(ins[s[i]])   continue;
            while(stk.size() && stk.back() > s[i] && last[stk.back()] > i){
    
                ins[stk.back()] = false;
                stk.pop_back();
            }

            ins[s[i]] = true;
            stk += s[i];
        }

        return stk;
    }
};