316. 去除重复字母

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

示例 1：

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

示例 2：

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

核心思路是单调栈 + 贪心算法，通过维护一个单调递增的栈来确保字典序最小，同时利用计数数组判断字符是否还有剩余，确保每个字符只保留一次：

  1. 预处理：
    • 统计字符串中每个字符的出现次数（count 数组）；
    • 记录字符是否已在栈中（in_stack 数组），避免重复添加。
  2. 单调栈逻辑：
    • 遍历字符串中的每个字符C：
      • 减少 count[c]（当前字符已被考虑）；
      • 若 c 已在栈中，直接跳过；
      • 若 c 不在栈中，且栈不为空，且栈顶字符大于 c，且栈顶字符在后续还有出现（count[栈顶字符] > 0），则弹出栈顶字符（确保字典序更小）；
      • 将 c 压入栈，并标记为已在栈中。
  3. 结果构建：
    • 栈中字符即为去重后字典序最小的结果，拼接后返回。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> count(26, 0);    // 统计每个字符的出现次数
        vector<bool> in_stack(26, false);  // 标记字符是否已在栈中
        string stack;  // 单调栈，存储结果字符
        
        // 统计字符出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        for (char c : s) {
            int idx = c - 'a';
            count[idx]--;  // 当前字符已被考虑，剩余次数减1
            
            if (in_stack[idx]) {  // 字符已在栈中，跳过
                continue;
            }
            
            // 栈非空，且栈顶字符大于当前字符，且栈顶字符后续还有出现
            while (!stack.empty() && stack.back() > c && count[stack.back() - 'a'] > 0) {
                in_stack[stack.back() - 'a'] = false;  // 标记为不在栈中
                stack.pop_back();  // 弹出栈顶字符
            }
            
            stack.push_back(c);  // 将当前字符压入栈
            in_stack[idx] = true;  // 标记为已在栈中
        }
        
        return stack;
    }
};