316.去除重复字母

316.去除重复字母

题目描述：

给出一个字符串 s，去除其中的重复字母，使得每个字母只出现一次。需要保证返回结果的字典序最小。

数据范围：
$1\le n \le 10^4$

题解：

维护一个单调增的栈，可以保证字典序。出栈时需要保证出栈的元素在后面还有，否则的话不满足每个字母都出现一次。因此需要事先记录每个字母出现的次数，然后在遍历时更新 $(i, n - 1]$ 里面字母出现的次数。

同时需要避开重复字符，使用数组记录当前栈中有哪些种类的字母，如果遇到了相同的，直接更新次数，不用入栈。

为了方便输出答案，直接使用字符串string来代替栈。

代码：

class Solution
{
public:
    static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }

    string removeDuplicateLetters(string s)
    {
        optimize_cpp_stdio();
        // 单调增栈
        // 后面字母还剩几个
        vector<int> mp(26, 0);
        // 当前是否已经存在该种字母
        vector<int> exist(26, 0);
        string st;
        int n = s.size();
        for (int i = 0; i < n; ++i)
            mp[s[i] - 'a']++;
        for (int i = 0; i < n; ++i)
        {
            if (exist[s[i] - 'a'])
            {
                mp[s[i] - 'a']--;
                continue;
            }
            while (st.size() && mp[st.back() - 'a'] > 0 && st.back() >= s[i])
            {
                exist[st.back() - 'a'] = false;
                st.pop_back();
            }
            st.push_back(s[i]);
            exist[s[i] - 'a'] = true;
            mp[s[i] - 'a']--;
        }
        return st;
    }
};