题目描述

这道题让我们移除重复字母，使得每个字符只能出现一次，而且结果要按字母顺序排，前提是不能打乱其原本的相对位置

样例

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

算法

(贪心) $O(n)$

这道题用栈来做。
栈中元素表示扫描到当前位置，当前出现的结果。
一个数组cnt记录字符串中字符出现的个数。
visit表示26个字符是否在当前的栈中。
对于每一个字符，先判断他是否在栈中，如果在栈中，那么直接去掉它。
如果不在栈中。 如果比栈末尾大，那么直接加在末尾。
如果比栈末尾小，这时候要弹出栈的末尾元素，弹出时要更新visit数组。
直到比栈末尾大这时候直接加上这个字符，并且维护visit。

时间复杂度： 对字符串扫描了一遍，所以复杂度为$O(n)$

C++ 代码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<bool> visit(26,false);
        vector<int> cnt;
        cnt.resize(26);

        for (auto c: s){
            cnt[c-'a']++;
        }
        string result = "";
        for(auto c:s){
            cnt[c-'a']--;
            if (visit[c-'a']) continue;
            while(!result.empty()&&result.back()>c&&cnt[result.back()-'a']>0){
                visit[result.back()-'a'] = false;
                result.pop_back();

            }
            result+=c;
            visit[c-'a'] =true;
        }

        return result;

    }
};