1. 问题背景与需求解析
字符串处理是编程面试和算法竞赛中的高频考点，而"去除重复字母"这个问题看似简单，实则暗藏玄机。题目要求我们从一个给定的字符串中去除重复字母，使得每个字母只出现一次，并且要保证结果的字典序最小，同时不能打乱其他字符的相对位置。这种约束条件下的字符串处理，在实际开发中其实很常见——比如数据库索引优化、日志去重等场景都会遇到类似需求。
我第一次遇到这个问题是在准备某大厂面试时，当时觉得"不就是去重嘛"，结果被面试官追问"如何保证字典序最小"时直接卡壳。后来才发现，这其实是一个经典的贪心算法与栈结构结合的题目，考察的是对数据结构的灵活运用能力。
2. 核心算法思路拆解
2.1 暴力解法与问题分析
最直观的想法可能是遍历字符串，遇到重复字符时保留字典序较小的那个。比如对于"bcabc"，看到第二个'b'时比较它与前一个'b'的字典序。但这种方法无法处理像"cbacdcbc"这样的复杂情况——当遇到第二个'c'时，我们需要考虑后面是否还有'a'和'd'，因为'a'的字典序更小。
这个认知让我明白，单纯的前后字符比较是不够的，必须要有全局视野。于是我开始思考如何记录每个字符的最后出现位置，这样在决定是否保留当前字符时，可以知道后面是否还有机会再遇到它。
2.2 贪心算法与单调栈的结合
最终的解决方案结合了贪心算法和单调栈的思想：
- 首先统计每个字符的最后出现位置（last_occurrence）
- 维护一个结果栈和一个记录字符是否在栈中的集合（visited）
- 遍历字符串时：
- 如果当前字符已在栈中，跳过
- 否则，不断弹出栈顶比当前字符大且后面还会出现的字符
- 将当前字符压栈并标记为已访问
这种做法的精妙之处在于：通过last_occurrence知道后面是否还有机会遇到某字符，通过单调栈保证字典序最小，通过visited集合避免重复。时间复杂度O(n)，空间复杂度O(1)（因为字母数量固定）。
3. C++实现详解
3.1 基础版本实现
cpp复制#include <string>
#include <stack>
#include <vector>
using namespace std;
string removeDuplicateLett