LeetCode 316. 去除重复字母
目录
题目描述
题意分析
给一个只含小写字母的字符串，要求删掉一些字符，使得剩下的字符串满足两个条件：每个出现过的字母恰好只保留一次；在所有满足前一个条件的方案中，字典序最小。
这里有两个硬性要求需要分清主次。「每个字母只保留一次」是必须满足的约束——原串中出现过的字母，一个都不能少，也不能多留；「字典序最小」是在约束之下的优化目标。换句话说，答案的字符集合是唯一确定的（就是原串的字符集合），长度也是唯一确定的（就是不同字母的个数），可变的只有这些字母的排列顺序，而这个顺序又必须是原串的子序列。
约束信号有两个值得注意。一是字符集只有 26 个小写字母，这意味着「是否已选」和「剩余多少个」都能用定长数组表示，空间是常数；同时也意味着答案长度不超过 26，规模极小。二是「子序列」这个隐含要求——不能任意重排，只能从左到右挑，这才让问题变得不平凡，否则直接把不同字母排序输出就完事了。
边界情形包括：原串本身已无重复，此时答案就是原串；原串是单一字母的重复，答案是那个字母本身；原串已经是递增的（如
"abc"），任何删除都不会更优，答案就是它自己。
解法：单调栈 + 剩余频次
核心思路
答案既要包含所有不同字母且每种只出现一次，又必须保持原串的相对顺序。若逐个枚举子序列，方案数是指数级；真正需要解决的是：看到一个更小字符时，能否撤销已经选入答案的较大字符。
用字符数组充当栈，并维护两类信息：
used[c]：字符c是否已经在栈中，保证答案不重复；remain[c]：当前位置之后还有多少个c，判断弹出后能否补回来。扫描字符
ch时，先减少它的remain。如果它已在栈中，跳过这个副本；否则，只要栈顶top > ch且remain[top] > 0，就弹出top。前一个条件保证把ch提前会让字典序严格变小，后一个条件保证top以后还能重新加入，不会丢失必需字符。任一条件不满足都不能弹。循环不变量是：栈内字符互不相同，且它是当前扫描进度下能够扩展成合法答案的最小前缀。每次弹栈都是一次安全的交换——用更小字符提前，同时把被弹字符留给后面的副本；不能弹的字符则要么不大于当前字符，要么已无后继，保留它是最优或唯一合法选择。因此扫描结束时，栈就是字典序最小的合法子序列。
注意这里的栈不保证最终严格递增。例如
"cbacdcbc"的答案是"acdb"，d > b仍要保留，因为扫描到b时d后面已没有副本。所谓单调栈，指的是按条件持续弹栈的处理方式。
解题步骤
- 先统计每个字母的总出现次数到
remain。- 准备
used数组和一个空栈。- 从左到右读取
ch，先执行remain[ch]--，使它表示“当前位置之后”的次数。- 若
used[ch]为真，当前副本不入栈，继续扫描。- 当栈顶比
ch大且栈顶字符后面仍会出现时，持续弹栈，并同步清除其used标记。- 将
ch入栈并标记为已使用；扫描结束后返回栈中字符串。以
"bcabc"为例：先得到栈"bc"；读到a时，c、b都比a大且后面各有一个副本，所以依次弹出，栈变成"a"；最后再加入后面的b、c，得到"abc"。若某个栈顶后面不再出现，即使它更大也不能弹。
代码实现
class Solution {
public String removeDuplicateLetters(String s) {
int[] remain = new int[26];
for (int i = 0; i < s.length(); i++) {
remain[s.charAt(i) - 'a']++;
}
boolean[] used = new boolean[26];
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int index = ch - 'a';
remain[index]--;
if (used[index]) {
continue;
}
while (stack.length() > 0) {
char top = stack.charAt(stack.length() - 1);
if (top <= ch || remain[top - 'a'] == 0) {
break;
}
used[top - 'a'] = false;
stack.deleteCharAt(stack.length() - 1);
}
stack.append(ch);
used[index] = true;
}
return stack.toString();
}
}
func removeDuplicateLetters(s string) string {
remain := make([]int, 26)
for i := range s {
remain[s[i]-'a']++
}
used := make([]bool, 26)
stack := make([]byte, 0, 26)
for i := range s {
ch := s[i]
index := ch - 'a'
remain[index]--
if used[index] {
continue
}
for len(stack) > 0 {
top := stack[len(stack)-1]
if top <= ch || remain[top-'a'] == 0 {
break
}
used[top-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, ch)
used[index] = true
}
return string(stack)
}
复杂度分析
- 时间复杂度：
O(n)。每个字符至多入栈一次、出栈一次，while的总弹栈次数不超过n。- 空间复杂度：
O(1)。题目只有 26 个小写字母，remain、used和最多含 26 个字符的栈都与n无关。
关键点总结
- 弹栈必须同时满足“字典序会变小”和“被弹字符以后还能补回”。
- 剩余次数要先减再判断，其语义才是“当前位置之后还剩多少”。
- 字符弹出时必须同步把
used恢复为false，否则后续副本无法入栈。for套while仍是O(n)，因为每个字符只会被弹出一次。- 栈不一定整体单调；没有后续副本的较大字符必须留下。
易错点总结
- 只比较大小，不检查剩余次数：在
"cbacdcbc"中会弹掉以后不再出现的d，最终答案缺字符。- 遇到重复字符后才减少
remain：跳过的副本没有被消费，后续会误判某字符仍可补回。- 弹栈只用
if："bcabc"读到a时需要连续弹出c和b；只弹一次会得到更大的前缀。- 弹出后不清除
used：被弹字符的后续副本仍被当作已使用，答案会缺字母。- 强行维持严格递增：
"cbacdcbc"的正确答案"acdb"本身并不递增；是否能弹还取决于后续副本。- 把字符排序后去重：会破坏子序列顺序，例如
"cbacdcbc"不能直接返回"abcd"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1081. 不同字符的最小子序列 | 中等 | 与本题完全同题，题面换了说法，可用同一份代码直接通过 |
| 402. 移掉 K 位数字 | 中等 | 弹栈条件从「后面还会出现」换成「剩余删除额度」，且允许保留重复数字 |
| 321. 拼接最大数 | 困难 | 在 402 的单序列取最优之上，还要枚举两数组的长度分配并做归并比较 |