刷题记录第五十一天-去除重复字母
题目要求的是字典序最小的结果。只需要理解一点就是按大小顺序排列的字符串的字典序就是最小的，如“abcd”这种。
解题思路如下：
- 首先明确要使用栈结构，并且是从栈底到栈顶递增，要尽可能保证递增，这样就能保证字典序最小。
- 在遍历每个字符时，我们的规则是：如果当前元素大于等于栈顶元素，直接入栈。如果当前元素小于栈顶元素，此时如果将当前元素入栈，会打破顺序。此时如果栈顶元素在后面还会出现（这里就需要一个visit数组记录每个字符最后出现的下标），就删掉这个栈顶元素，保证当前元素入栈后递增不会破坏，这个过程是持续比较。直到当前元素大于等于栈顶元素。如果栈顶元素在后面不会出现，就只能保留这个栈顶元素。
- 需要考虑另外一个问题，如果当前元素在栈里面，那么这个元素一定不是某一个顺序字符串的最后一个元素(因为如果出现了顺序被打乱的情况，那么证明前面顺序字符串的最后一个元素在后面肯定不会出现了，所以才会打乱)，也就没有替换的必要。因此，如果当前元素在栈里面，就直接跳过这个元素。所以需要有另一个数组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;}
};