题解 | 去除重复字母

#include <stack>
#include <string>
class Solution {
public:
    string removeDuplicateLetters(string str) {
        int n = str.size();

        stack<char> stk;

        vector<int> last_apper(26, 0);  //记录字母是否已经保留了一个；
        vector<int> visited(26, 0);

        for(int i=0; i<n; ++i){ //记录每种字母最后一次出现的位置
            last_apper[str[i] - 'a'] = i;
        }

        for(int i=0; i<n; ++i){
            if( visited[str[i]-'a'] ){  //如果这个字母已经保存过了，跳过
                continue;
            }

            //栈是我们保留需要的字符串
            //若当前字符小于栈顶（字符串尾部）表示字符串的字典序还可以更小，
            //但得保证栈顶要弹出的字母后续还有, 用到字母最后出现位置记录数组；/
            //贪心算法，局部最优就是全局最优，当 当前是更小的字母则一位一位替换，栈中是当前最优（字典序最小）
            while( !stk.empty() && str[i] < stk.top() && i < last_apper[stk.top()-'a']){
                visited[stk.top() - 'a'] = 0; //弹出后，更改为未使用
                stk.pop();
            }

            stk.push(str[i]);
            visited[str[i] - 'a'] = 1; //进入，已使用；
        }

        string s;
        while (!stk.empty()) {
            s = stk.top() + s;
            stk.pop();
        }

        return s;
    }
};