C语言重构【316/1081】去除重复字母/不同字符的最小子序列

妖狐艹你老母 2022-11-07 04:16 189阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
    
    注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
    
    
    示例 1：
    输入：s = "bcabc"
    输出："abc"
    示例 2：
    
    输入：s = "cbacdcbc"
    输出："acdb"
     
    提示：
    1 <= s.length <= 104
    s 由小写英文字母组成
    
    
    1081题表述如下：
    返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

#### 方案： ####

*  单调栈：[个人理解][Link 1]

class Solution
    { 
    public:
        string removeDuplicateLetters(string s)
        { 
            int len = s.size();
            vector<int> hash(26, 0);
            vector<int> used(26, 0);
            //数组栈，index为指针
            vector<char> sta(26, 96);
            int index = 0;
            //记录出现次数
            for (int i = 0; i < len; i++)
            { 
                hash[s[i] - 'a']++;
            }
            sta[0] = s[0];
            hash[s[0] - 'a']--;
            used[s[0] - 'a']++;
            for (int i = 1; i < len; i++)
            { 
                //当前值没用过+当前值比栈顶小+栈顶的值后面还有一个
                while (index >= 0 && sta[index] > s[i] && hash[sta[index] - 'a'] > 0 && used[s[i] - 'a'] == 0)
                { 
                    used[sta[index] - 'a'] = 0;
                    index--;
                }
                if (used[s[i] - 'a'] == 0)
                { 
                    //入场
                    sta[++index] = s[i];
                    used[s[i] - 'a'] = 1;
                }
                hash[s[i] - 'a']--;
            }
            string res;
            res.assign(sta.begin(), sta.begin() + index + 1);
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[Link 1]: https://blog.csdn.net/symuamua/article/details/114649796