LeetCode 第316题：去除重复字母

📖 文章摘要

本文详细解析LeetCode第316题“去除重复字母”，这是一道字符串处理和贪心算法的问题。文章提供了基于栈和贪心的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升字符串处理能力的程序员。

核心知识点： 贪心算法、栈、字符串处理
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升字符串处理能力的程序员

题目描述

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

示例

示例 1：

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

示例 2：

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

提示

1 <= s.length <= 10^4
s 由小写英文字母组成

解题思路

方法：贪心 + 栈

这道题可以使用贪心算法结合栈来解决。我们需要保证字典序最小的同时去除重复字母。

关键点：

使用栈来维护结果字符串
记录每个字符的最后出现位置
使用visited数组记录字符是否已在栈中
贪心选择：当前字符小于栈顶且栈顶字符后面还会出现时，可以删除栈顶

具体步骤：

统计每个字符的最后出现位置
遍历字符串，对每个字符：
- 如果已在栈中，跳过
- 当栈不为空，且当前字符小于栈顶，且栈顶字符后面还会出现时，弹出栈顶
- 将当前字符入栈
将栈中元素组合成结果字符串

时间复杂度：O(n) 空间复杂度：O(1)，因为字符集大小固定

图解思路

栈的状态变化分析表

步骤	当前字符	栈状态	操作	说明
初始状态	-	[]	-	空栈
1	‘b’	[b]	入栈	第一个字符直接入栈
2	‘c’	[b,c]	入栈	字典序正确，入栈
3	‘a’	[a]	出栈并入栈	a小于bc且bc后面还会出现，弹出bc
4	‘b’	[a,b]	入栈	字典序正确，入栈
5	‘c’	[a,b,c]	入栈	字典序正确，入栈

字符出现位置分析表

字符	最后出现位置	是否可重复出现
‘a’	2	是
‘b’	3	是
‘c’	4	是

代码实现

C# 实现

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        int[] lastPos = new int[26];
        bool[] visited = new bool[26];
        Stack<char> stack = new Stack<char>();
        
        // 记录每个字符的最后出现位置
        for (int i = 0; i < s.Length; i++) {
            lastPos[s[i] - 'a'] = i;
        }
        
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!visited[c - 'a']) {
                while (stack.Count > 0 && c < stack.Peek() && 
                       lastPos[stack.Peek() - 'a'] > i) {
                    visited[stack.Pop() - 'a'] = false;
                }
                stack.Push(c);
                visited[c - 'a'] = true;
            }
        }
        
        // 构建结果字符串
        char[] result = stack.ToArray();
        Array.Reverse(result);
        return new string(result);
    }
}

Python 实现

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last_pos = {}
        # 记录每个字符的最后出现位置
        for i, c in enumerate(s):
            last_pos[c] = i
            
        stack = []
        visited = set()
        
        for i, c in enumerate(s):
            if c not in visited:
                while stack and c < stack[-1] and i < last_pos[stack[-1]]:
                    visited.remove(stack.pop())
                stack.append(c)
                visited.add(c)
                
        return ''.join(stack)

C++ 实现

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> lastPos(26, 0);
        vector<bool> visited(26, false);
        string stack;
        
        // 记录每个字符的最后出现位置
        for (int i = 0; i < s.length(); i++) {
            lastPos[s[i] - 'a'] = i;
        }
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            if (!visited[c - 'a']) {
                while (!stack.empty() && c < stack.back() && 
                       lastPos[stack.back() - 'a'] > i) {
                    visited[stack.back() - 'a'] = false;
                    stack.pop_back();
                }
                stack.push_back(c);
                visited[c - 'a'] = true;
            }
        }
        
        return stack;
    }
};

执行结果

C# 实现

执行用时：76 ms
内存消耗：36.2 MB

Python 实现

执行用时：36 ms
内存消耗：15.1 MB

C++ 实现

执行用时：0 ms
内存消耗：6.3 MB

性能对比

语言	执行用时	内存消耗	特点
C#	76 ms	36.2 MB	实现简洁，性能适中
Python	36 ms	15.1 MB	代码最简洁，性能良好
C++	0 ms	6.3 MB	性能最优，内存占用最小

代码亮点

🎯 使用栈和贪心算法的巧妙结合
💡 通过visited数组避免重复处理
🔍 利用lastPos数组优化判断逻辑
🎨 代码结构清晰，变量命名直观

常见错误分析

🚫 没有正确处理字符的相对顺序
🚫 忘记检查字符是否已在结果中
🚫 栈操作时没有更新visited状态
🚫 没有考虑字典序最小的要求

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
贪心+栈	O(n)	O(1)	时间和空间复杂度都很优秀	实现逻辑相对复杂
递归	O(n^2)	O(n)	思路直观	性能较差

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第316题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法：贪心 + 栈

图解思路

栈的状态变化分析表

字符出现位置分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流