LeetCode 316. 去除重复字母——单调栈+字典序+贪心的组合

适读人群：Java 中高级工程师、备战大厂面试的同学 | 阅读时长：约22分钟 | 难度：中等偏难

---

开篇故事

这道题是我见过把单调栈用得最漂亮的题之一。看上去是个字符串题，其实核心是贪心+单调栈，而且加入了一个「每种字母必须且只出现一次」的约束，让题目变得有意思很多。

我第一次做这道题的时候，把它当成了纯排序问题，想着直接对字符排序不就得了？然后发现不行，因为要保持原始相对顺序。然后想到了暴力递归，发现超时。最后才想到：贪心地用单调栈维护一个字典序最小的序列，遇到可以替换的字符就替换。

这道题考察的是一个组合能力：你需要同时理解贪心思想（什么时候可以删、什么时候不能删）、单调栈维护（如何高效实现）、字符频率统计（什么时候字符还有剩余可以删除）。三者缺一不可。

---

一、题目解析

题目描述：

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

示例：

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

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

约束：

• 只包含小写英文字母
• 1 <= s.length <= 10^4

核心理解：

1. 每种字母在结果中必须恰好出现一次
2. 字符的相对顺序不能改变（不是重新排列，只是选择保留哪些）
3. 在满足前两个条件下，字典序最小

---

二、解法一：暴力递归/回溯

思路分析

对于字符串的每个位置，决定「留下」还是「跳过」（如果后面还有相同字符）。枚举所有合法的方案，取字典序最小的。

class Solution {
    private String result = null;
    
    public String removeDuplicateLetters(String s) {
        // 统计每种字符出现的次数
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        
        backtrack(s, 0, new StringBuilder(), count, new boolean[26]);
        return result;
    }
    
    private void backtrack(String s, int idx, StringBuilder curr, 
                           int[] count, boolean[] used) {
        if (idx == s.length()) {
            // 检查是否每种字符都出现了一次
            boolean valid = true;
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0 && !used[i]) { valid = false; break; }
            }
            if (valid) {
                String candidate = curr.toString();
                if (result == null || candidate.compareTo(result) < 0) {
                    result = candidate;
                }
            }
            return;
        }
        
        char c = s.charAt(idx);
        count[c - 'a']--;
        
        if (used[c - 'a']) {
            // 已经选过，跳过
            backtrack(s, idx + 1, curr, count, used);
        } else {
            // 可以选，也可以跳过（如果后面还有）
            used[c - 'a'] = true;
            curr.append(c);
            backtrack(s, idx + 1, curr, count, used);
            curr.deleteCharAt(curr.length() - 1);
            used[c - 'a'] = false;
            
            if (count[c - 'a'] > 0) {
                // 跳过当前，后面还有
                backtrack(s, idx + 1, curr, count, used);
            }
        }
        
        count[c - 'a']++;
    }
}

这个暴力解法时间复杂度极高，指数级别，只能作为思路验证，不能实际使用。

复杂度分析

• 时间复杂度：O(2^n)。指数级。
• 空间复杂度：O(n)。

---

三、解法二：贪心 + 每次找最优起始字符

思路分析

换一个贪心角度：每次从前缀中选择字典序最小的字符，且该字符后面的子串中包含所有剩余字符。

具体来说，把问题转化为：在满足「剩余子串中还包含所有未选字符」的前提下，选择当前位置能选的最小字符。

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {
        if (s.isEmpty()) return s;
        
        // 统计每种字符的出现次数
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        
        // 找到可以作为起始字符的位置：最小字符，且其后的子串包含所有其他字符
        int minIdx = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(minIdx)) minIdx = i;
            // 当某种字符的计数减到0时，该字符后面不再出现，必须在这之前做决定
            if (--count[s.charAt(i) - 'a'] == 0) break;
        }
        
        // 选择 minIdx 处的字符，递归处理其后的子串（去掉已选字符的出现）
        String remaining = s.substring(minIdx + 1)
            .replaceAll(String.valueOf(s.charAt(minIdx)), "");
        
        return s.charAt(minIdx) + removeDuplicateLetters(remaining);
    }
}

复杂度分析

• 时间复杂度：O(n × 26)。每次递归处理一层，每层 O(n)，最多 26 个不同字符，所以 O(26n)。
• 空间复杂度：O(n)。递归深度最大 26。

---

四、解法三（最优）：单调栈 + 贪心

核心思想

用单调栈维护当前已选字符序列，保持字典序最小。

贪心逻辑：

• 当处理字符 c 时，如果 c 比栈顶字符 top 的字典序小，并且 top 在后面还会出现（即 top 的剩余计数 > 0），那么可以把 top 从结果中删掉，换成 c——这样字典序更小，而且 top 以后还能再被选进来。
• 如果 c 已经在栈中（已被选），直接跳过（不能重复）。

用到的数据结构：

• remain[26]：每种字符在当前位置之后（包括当前）的剩余次数
• inStack[26]：布尔数组，标记某字符是否已在栈中
• 单调递增栈（字典序）：存字符

完整代码

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {
        int n = s.length();
        
        // 统计每种字符的总出现次数（代表剩余次数，随遍历递减）
        int[] remain = new int[26];
        for (char c : s.toCharArray()) remain[c - 'a']++;
        
        // 标记字符是否已在栈中
        boolean[] inStack = new boolean[26];
        
        // 单调栈（字典序递增），存字符
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            remain[c - 'a']--; // 先减，表示当前位置之后的剩余次数
            
            if (inStack[c - 'a']) {
                // 字符 c 已在结果中，跳过
                continue;
            }
            
            // 贪心：弹出字典序更大且后面还有机会出现的字符
            while (!stack.isEmpty() 
                   && c < stack.peek() 
                   && remain[stack.peek() - 'a'] > 0) {
                char top = stack.pop();
                inStack[top - 'a'] = false;
            }
            
            stack.push(c);
            inStack[c - 'a'] = true;
        }
        
        // 栈底到栈顶是字典序递增的，但 Deque 的 push 是头插
        // 所以要反转输出
        StringBuilder sb = new StringBuilder();
        for (char c : stack) sb.append(c);
        return sb.reverse().toString();
    }
}

手动模拟

以 s = "cbacdcbc" 为例：

初始 remain = {a:1, b:2, c:4, d:1}

字符	remain（处理前→后）	栈	操作
c	c:4→3	[c]	c入栈
b	b:2→1	[c] → [b]	b<c 且 remain[c]=3>0，弹c；b入栈
a	a:1→0	[b] → [a]	a<b 且 remain[b]=1>0，弹b；a入栈
c	c:3→2	[a,c]	a<c 不弹；c入栈
d	d:1→0	[a,c,d]	d>c 不弹；d入栈
c	c:2→1	[a,c,d]	c已在栈中，跳过
b	b:1→0	[a,c,d]	b<d 但 remain[d]=0，不能弹d；b不能入（会导致 a,b,c,d 顺序错）等一下...

等等，这里需要重新理解：b < d 且 remain[d]=0，所以不能弹d（d后面没有了，必须保留）。b < c 且 remain[c]=1>0，但d在c上面，d不弹的话c也不弹。所以b只能排在d后面？

但是b在栈里的位置在d后面，题目要求保留原序，所以b只能放在d后。最终结果是 a,c,d,b → "acdb"。

让我重新模拟（栈底在左，栈顶在右）：

字符	栈状态	操作
c	[c]	入栈
b	[b]	b<c 且c后面还有（3>0），弹c，b入
a	[a]	a<b 且b后面还有（1>0），弹b，a入
c	[a,c]	c>a，入栈
d	[a,c,d]	d>c，入栈
c	[a,c,d]	c已在栈，跳过
b	[a,c,d,b]	b<d 但remain[d]=0不能弹；直接入
c	[a,c,d,b]	c已在栈，跳过

反转栈输出：a,c,d,b → "acdb"，正确！

复杂度分析

• 时间复杂度：O(n)。每个字符最多入栈出栈各一次，O(n)。字母表大小是常数 26。
• 空间复杂度：O(1)。栈和辅助数组大小最多 26（常数级）。

---

五、举一反三

这道题的模式：「保持相对顺序 + 字典序最小 + 每种元素出现次数限制」 是一类题的共同特征：

题目	变体
316. 去除重复字母	每种字母恰好一次
1081. 不同字符的最小子序列	与316完全相同
402. 移掉K位数字	移掉k个数字，字典序最小（下一篇）
321. 拼接最大数	两数组合并最大子序列

---

六、踩坑实录

坑一：先减 remain 再判断是否在栈中

遍历时要先 remain[c-'a']--，再判断 if (inStack[c-'a'])。如果先判断再减，那么跳过的字符的 remain 就没有减，会导致后续的弹出判断出错（以为某字符后面还有，其实已经用完了）。

// 正确顺序
remain[c - 'a']--; // 先减
if (inStack[c - 'a']) continue; // 再判断

// 错误顺序
if (inStack[c - 'a']) continue; // 先判断，remain 没减
remain[c - 'a']--;

坑二：输出时要反转

用 Deque 模拟栈时，push 是头插（addFirst），peek 是看头部。遍历 Deque 是从头到尾，也就是从栈顶到栈底——与正确顺序相反。

所以最后要反转：sb.reverse()。或者改用 addLast/removeLast/peekLast，这样遍历就是从栈底到栈顶。

坑三：弹出条件同时需要「字典序更大」和「后面还有」

弹出栈顶 top 的条件是：

1. c < top：当前字符字典序更小，替换掉 top 可以让结果更好
2. remain[top] > 0：top 在后面还会出现，弹掉了还能再选

两个条件缺一不可。只满足条件1，如果 top 是最后一次出现，弹掉就再也加不进来了，违反了「每种字母必须出现」的要求。

---

七、总结

这道题是单调栈在字符串场景下的经典应用，三个关键要素同时起作用：

• 单调栈：维护字典序递增的字符序列
• 贪心：遇到更小的字符且后面还有机会，就弹出较大的
• 计数数组：判断是否「后面还有机会」以及「是否已在结果中」

写出这道题的最优解，就算基本掌握了单调栈在构造类问题中的用法。