LeetCode 补充题 166. 去除重复字母的最大字典序子序列
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 316. 去除重复字母
:::
给定小写英文字母字符串
s，删除若干字符，使结果包含原串中的每种字母且恰好一次。在所有满足条件的子序列中，返回字典序最大的一个。
示例 1：
输入：
s = "abacb"
输出："bac"
解释： 保留第二、三、四个字符，包含a、b、c各一次，且不能在保留顺序的条件下得到c开头的合法答案。
示例 2：
输入：
s = "bcabc"
输出："cab"
解释： 选择中间的c和末尾的a、b。
提示：
- 只允许删除，不能打乱剩余字符顺序。
- 空串返回空串。
题意分析
要让字典序最大，应尽量把较大的字母放在前面；但每种字母必须保留一次，不能直接排序，也不能删掉以后无法补回的字母。需要同时掌握当前结果和后续可用字符。
解法：可恢复字符的贪心单调栈
核心思路
[!blue]
remaining表示当前位置之后各字母的剩余次数，used表示字母是否已在结果栈中。读取字符先减少剩余次数，若已在栈中就跳过，保证结果不重复。新字符
c大于栈顶时，若栈顶在后面还会出现，就可弹出它并清除used，让更大的c提前，旧字母以后再补。这在第一个变化位置严格改善字典序，同时不破坏所有字母最终可选的条件。如果栈顶不小于
c，弹出不会变优；如果剩余次数为 0，弹出会永久漏字母，两种情况都必须停止。栈按扫描顺序接收字符，保留子序列顺序，每个输入位置最多入栈、出栈一次。
解题步骤
- 先统计所有字母的剩余次数。
- 读取字符时减少其剩余次数；已在栈中则跳过。
- 新字符更大且栈顶以后还能出现时弹栈，再把新字符入栈并标记。
代码实现
class Solution {
public String largestDistinct(String s) {
int[] remaining = new int[26];
boolean[] used = new boolean[26];
for (char c : s.toCharArray()) {
remaining[c - 'a']++;
}
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
int index = c - 'a';
remaining[index]--;
if (used[index]) {
continue;
}
while (stack.length() > 0) {
char top = stack.charAt(stack.length() - 1);
if (top >= c || remaining[top - 'a'] == 0) {
break;
}
used[top - 'a'] = false;
stack.setLength(stack.length() - 1);
}
stack.append(c);
used[index] = true;
}
return stack.toString();
}
}
func largestDistinct(s string) string {
remaining := [26]int{}
used := [26]bool{}
for _, c := range []byte(s) {
remaining[c-'a']++
}
stack := []byte{}
for _, c := range []byte(s) {
index := c - 'a'
remaining[index]--
if used[index] {
continue
}
for len(stack) > 0 {
top := stack[len(stack)-1]
if top >= c || remaining[top-'a'] == 0 {
break
}
used[top-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, c)
used[index] = true
}
return string(stack)
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：字符集合固定为 26 个时，辅助空间 $O(1)$；Java 转字符数组的实现另占 $O(n)$。
关键点总结
[!green]
只有被弹出的字母还能在后面补回时，才可以让更大字母提前；used 与剩余次数分别保证不重复和不遗漏。
易错点总结
[!yellow]
只有栈顶字符在后面还会出现时才能弹出，否则会漏掉必须保留的字母。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 316. 去除重复字母 | 中等 | 同样利用剩余次数决定能否弹栈，把弹栈比较方向反转即可从最小字典序改为最大字典序。 |
| 402. 移掉 K 位数字 | 中等 | 同样贪心弹出不利的栈顶，原题按删除次数限制，本题按每种字母至少保留一次限制。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！