刷题记录第五十一天-去除重复字母

题目要求的是字典序最小的结果。只需要理解一点就是按大小顺序排列的字符串的字典序就是最小的，如“abcd”这种。
解题思路如下：

1. 首先明确要使用栈结构，并且是从栈底到栈顶递增，要尽可能保证递增，这样就能保证字典序最小。
2. 在遍历每个字符时，我们的规则是：如果当前元素大于等于栈顶元素，直接入栈。如果当前元素小于栈顶元素，此时如果将当前元素入栈，会打破顺序。此时如果栈顶元素在后面还会出现（这里就需要一个visit数组记录每个字符最后出现的下标），就删掉这个栈顶元素，保证当前元素入栈后递增不会破坏，这个过程是持续比较。直到当前元素大于等于栈顶元素。如果栈顶元素在后面不会出现，就只能保留这个栈顶元素。
3. 需要考虑另外一个问题，如果当前元素在栈里面，那么这个元素一定不是某一个顺序字符串的最后一个元素(因为如果出现了顺序被打乱的情况，那么证明前面顺序字符串的最后一个元素在后面肯定不会出现了，所以才会打乱)，也就没有替换的必要。因此，如果当前元素在栈里面，就直接跳过这个元素。所以需要有另一个数组last来记录哪些字符在栈里面。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int n=s.size();
        vector<bool> visited(26);
        vector<int> last(26);
        for(int i=0;i<n;i++){
            last[s[i]-'a']=i;
        }
        stack<char> stk;
        for(int i=0;i<n;i++){
            if(visited[s[i]-'a'])continue;
            if(!stk.empty())
            while(!stk.empty()&&s[i]<stk.top()&&last[stk.top()-'a']>i){
                visited[stk.top()-'a']=false;
                stk.pop();
            }
            stk.push(s[i]);
            visited[s[i]-'a']=true;
        }
        string result(stk.size(), 'c' );
        for(int i=stk.size()-1;i>=0;i--){
            result[i]=stk.top();
            stk.pop();
        }
        return result;
    }
};