题解 | 去除重复字母

316. 去除重复字母：原题链接。

题意：

     给你一个字符串s，删除字符串中重复的字符，使新字符串的字典序最小（不能打乱字符串原顺序），且原字符串中出现的字符都要有且仅有一个。

做题思路：

     通过题目，我们可以得知想要拿到字典序最小的字符串，只要遍历字符串并用栈读入，便利点时重复循环：当栈顶的字符大于当前字符时，就删除该字符，直到当前字符不大于栈顶或栈为空时，停止循环。这样就可以得到最小的字典序字符串。

     但题目要求，每个出现在字符串中的字符都要出现一次，所以我们需要对字符串进行统计，当进行删除操作时，判断当前字符位置之后是否还有该字符，如果不存在，则停止删除，结束循环，还存在则继续循环。

     由此可以得出以下代码:

string removeDuplicateLetters(string s) {
    int n=s.size();
    stack<char>q;
    //cnt用以记录字符串个数
    vector<int>cnt(30,0);
    //vis用来标记字符串，判断字符是否被选中
    vector<int>vis(30,0);
    //统计各个字符的个数 
    for (int i=0;i<n;i++)cnt[s[i]-'a']++;
    for (int i=0;i<n;i++)
    {
    	//每次遍历减去当前字符个数 
        cnt[s[i]-'a']--;
        //如果已经选择字符中已经有过该字符则跳过本次循环 
        if (vis[s[i]-'a'])continue;
        /*
        	循环的三个条件含义分别是：
			1.!q.empty()：当栈为空时，停止循环，防止越界
			2.s[i]<q.top()：当当前字符的大小小于当前字符串的末尾字符时进行循环
			3.cnt[q.top()-'a']：当cnt计数为0时，说明此时该字符之后已经没有相同字符了，必须保留	 
        */
        while(!q.empty() && s[i]<q.top() && cnt[q.top()-'a'])
        {
        	//删出栈顶中的字符，并修改标记 
            vis[q.top()-'a']=0;
            q.pop();
        }
        //将选中的字符放入栈顶并标记 
        q.push(s[i]);
        vis[s[i]-'a']=1;
    }
    //将字符从栈顶拿出并逆序记录 
    string a="";
    for (int i=0;i<q.size();)
    {
        a=q.top()+a;
        q.pop();
    }
    return a;
}