316. Remove Duplicate Letters

[namespace-io]

贪心算法复杂度O(n)最多递归26次

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string r;
        if(s.size() == 0) return r;
        
        int a[26] = {0};
        int idx = 0, i;
        for(auto c : s) a[c-'a']++;
        for(i = 0; i < s.size(); i++){
            if(s[idx] > s[i]) idx = i;
            if(--a[s[i] - 'a'] == 0) break;
        }
        r += s[idx];
        auto t = s.substr(idx+1);
        t.erase(remove(t.begin(), t.end(), s[idx]), t.end());
        return r + removeDuplicateLetters(t);
    }
};

可以用单调递增栈做，单调递增栈的性质是可以求出左边第一个比其小的数
由于每个元素至少出现一次的限制，栈中其实并不是单调的，而是分段单调的
同时还要保证栈中的元素唯一
当栈顶的元素是最后一个元素，不能弹出，这就是分段的来源

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string st;
        
        int a[26] = {0};
        bool f[26] = {false};
        int idx;
        for(auto c : s) a[c-'a']++;
        
        for(int i = 0; i < s.size(); i++){
            idx = s[i] - 'a';
            a[idx]--;
            if(f[idx] == true) continue;
            while(!st.empty() && st.back() >= s[i] && a[st.back() - 'a'] > 0){
                f[st.back() - 'a'] = false;
                st.pop_back();
            }
            
            st.push_back(s[i]);
            f[idx] = true;
        }
        
        return st;
    }
};