2023-11-27

去除重复字母-力扣316

题目

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

1 2	输入：s = "bcabc" 输出："abc"

示例 2：

1 2	输入：s = "cbacdcbc" 输出："acdb"

提示：

1 <= s.length <= 104
s 由小写英文字母组成

解析

思路：贪心+单调栈

要解决这个题，首先得明白什么是字典序列。字典项就是对字符串的排序，从头开始，挨个比对每个字符，优先级从左到右依次降低，字符排在前面的字符串小。如abc < acb，abcc<acba,字典序大小和长度无关。

先来看第一个样例，不要拿整个串来分析，我们一个一个看，逐步扩展得到答案。第一个字符是‘b’，如果只有它的话，那它自己就是答案，所以暂时不动。接下来再看“bc”，“bc”及是包含b，c两个字母的最小字典序，它也暂时不动。看“bca”，这时矛盾出现，“bca”不是最小字典序，所以如果a后面还有c，那么我们就应该抛弃a前面的c，这时“bca”–>“ba”,同理，如果a后面还有b，我们也应该抛弃b。

很明显，a前面的字符符合先进后出的规律，直接想到栈结构。此时我们相当于维护了一个栈内元素分组递增的栈，这便是单调栈。（实际上单调栈内元素不一定分组递增，满足单调性即可）

再来看第二个样例，当我们按上面思路分析到d的时候，虽然这时字符串不是最小字典序，但是d只出现了一次，题目要求不能改变字符相对位置，所以对于只出现一次的字符，我们不能抛弃。这也就是为什么栈内元素是分组递增的

最后说说贪心的体现：我们希望得到最小字典序，那么就要使答案字符串中位置靠前的字符尽可能地小，当我们从小到大扩展分析问题时，它的等价论述是要使答案字符串的尾字符尽可能的小，因为字符串中的每个字符都曾经是尾字符，所以二者等价。单调栈正是实现了这一点。

代码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> vis(26),num(26);//vis标记栈内的元素，num表示字符串中各个字符的出现次数
        for(char ch : s)
        {
            num[ch-'a']++;
        }
        string stk;
        for(char ch:s)
        {
            if(!vis[ch-'a'])
            {
                while(!stk.empty()&&stk.back()>ch)
                {
                    if(num[stk.back()-'a']>0)
                    {
                        vis[stk.back()-'a'] = 0;
                        stk.pop_back();
                    }
                    else
                     break;
                }
                vis[ch-'a'] = 1;
                stk.push_back(ch);
            }
            num[ch-'a'] -= 1;
        }
        return stk;
    }
};