问题描述

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

解题思路

本题的本质是：在保持原字符串中每个字符相对顺序的前提下，选出一个字典序最小的子序列，且每个字符恰好出现一次。这是经典的单调栈 + 贪心问题。

核心思路

  1. 统计每个字符的出现次数：用 count[26] 数组记录每个字符在剩余字符串中还剩多少个。这是判断”能否丢弃当前字符”的关键依据。

  2. 维护单调递增栈：遍历字符串，对于每个字符 c：

    • 将 count[c] 减 1
    • 如果 c 已经在栈中，跳过（确保每个字符只出现一次）
    • 如果 c 不在栈中，检查栈顶字符 top：
      • 如果 top > c（栈顶字符字典序大于当前字符）且 count[top] > 0（后续还会出现 top），则可以将 top 弹出。因为我们可以后面再添加 top，这样能让结果字典序更小
      • 重复以上检查，直到栈为空或栈顶不能再弹出
    • 将 c 压入栈

  3. 结果输出：栈中从底到顶就是最终结果的逆序，反转后得到答案。

举例说明

以输入 s = "bcabc" 为例：

步骤 当前字符 count 状态 栈状态 说明
初始化 - b:4, c:2, a:1 []
i=0 ‘b’ b:3, c:2, a:1 [b] 栈空，直接压入
i=1 ‘c’ b:3, c:1, a:1 [b,c] c > b，压入
i=2 ‘a’ b:3, c:1, a:0 [a] a < c 且 c 后面还有(c:1>0)，弹出 c；a < b 且 b 后面还有(b:3>0)，弹出 b；压入 a
i=3 ‘b’ b:2, c:1, a:0 [a,b] b > a，压入
i=4 ‘c’ b:2, c:0, a:0 [a,b,c] c > b，压入

结果："abc"，字典序最小。

为什么用单调栈？

贪心策略：对于相邻的两个字符，如果前一个字符字典序更大，且它之后还会再出现，那么丢弃它能让结果字典序更小。这天然适合用单调递增栈来维护。

复杂度分析

  • 时间复杂度：O(n)，每个字符最多入栈出栈一次。
  • 空间复杂度：O(1)，虽然使用了栈和计数数组，但它们的大小仅取决于字符集大小（26 个小写字母），是常数级别。

代码

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
package code.J316;

import java.util.*;

public class J316 {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']--;
            if (stack.contains(s.charAt(i))) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > s.charAt(i) && count[stack.peek() - 'a'] > 0) {
                stack.pop();
            }
            stack.push(s.charAt(i));
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}