316. 去除重复字母

316. 去除重复字母

前置知识：

​ 对于一个字符串，如果要从中去除一个字符使得字符串的字典序最小。那么需要去除的是最靠左边的一个s[i] > s[i + 1]的字符串，因为最前面的最字典序影响最大。这个s[i]称为关键字符。

本题不能打乱原来的顺序，且每个字母只出现一次，因为所需的是从头开始遍历，处理遍历到的所有的关键字符。

维护一个栈

1. 当栈顶>当前字符时候，删除栈顶。但是因为每个字母都要出现一次，因此当后面这个栈顶字母不再出现时，就不能删除。
2. 当栈顶<当前字符时候，压入栈，但由于不能重复，所以如果栈中已有同个字符，就不压入。
3. 当相等时，不能压入，因为不能重复。

为什么要用栈呢

为了维护字符间以及字符删除后的相邻关系以及字符删除后继续维持原来的顺序，栈是一个非常适合的数据结构。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int visited[26]{ 0 };
        int num[26]{ 0 };
        int sz = s.size();
        for(auto& ch : s)
            ++num[ch - 'a'];
        stack<char> st;
        for(auto& ch : s)
        {
            if(!visited[ch - 'a']) // 如果前面有了，就不加了，加入假设前面这个万一会被丢掉，那现在加的也绝对会被丢，如果前面那个是个有效的，那说明现在这个一定会被丢，因为肯定重复或者构成了逆序。
            {
                while(!st.empty() && st.top() > ch && num[st.top() - 'a'] != 1)
                {
                    --num[st.top() - 'a'];
                    visited[st.top() - 'a'] = 0;
                    st.pop();
                }
                st.push(ch);
                visited[ch - 'a'] = 1;
            }else // 直接错过了都没机会去栈里待待
                --num[ch - 'a'];
        }
        string ret(st.size(), ' ');
        int index = st.size() - 1;
        while(!st.empty())
        {
            ret[index--] = st.top();
            st.pop();
        }
        return ret;
    }
};