刷到 LeetCode 第3816题“删除重复字符后的字典序最小字符串”时我第一反应是这题不是白给吗字符串去重我闭着眼都会。结果真动手写的时候才发现“字典序最小”这四个字才是整套题的真考点去重只是表面工作顺序约束才是暗中使绊子的地方。这一题非常适合放在单调栈主题里练手做完之后你会对“贪心 栈”的组合拳理解深一大截。如果你正在准备算法面试或者刷题进度卡在字符串类问题上这篇内容可以帮你省掉不少弯路。我会从题目本身的约束讲起拆清楚为什么不能简单去重排序然后给出标准解法——基于单调栈的线性算法并且把我实际调试过程中踩过的几个坑、以及验证正确性用的暴力对拍方法一并写出来最后再聊聊这一类题的通用识别特征。这里先给结论时间复杂度 O(n)空间复杂度 O(n)属于介乎中等和困难之间的经典题。题面看起来短背后的贪心决策一点都不简单。1. 题目拆解三个条件其实在互相打架1.1 表面意思 vs 真实约束先别急着写代码把题面翻译成三句话输入一个字符串里面同一个字符可能出现多次你要删掉一些字符让每个字符最后只剩一次删完之后剩下的字符串必须字典序最小。很多人包括我第一眼会跳过一个小小的隐藏条件删除字符不会改变剩下字符的相对顺序。也就是说最后输出的字符串必须是原字符串的一个子序列不能是字符集合随便排序的结果。这是什么概念呢拿 s cbacdcbc 举例字符集合是 {a,b,c,d}如果你直接 sorted(set(s))得到 abcd这个字符串看起来字典序很小但它不是 cbacdcbc 的子序列——在原串里面a 后面紧跟着 cc 后面才到 dd 后面才是 b永远组不成 a-b-c-d 这种顺序。所以这条路一开始就堵死了。那能不能“保留每个字符第一次出现的位置”呢同样用这个例子第一次出现的顺序是 c、b、a、d输出 cbad。它是原串的子序列每个字符也都只出现一次但字典序还不是最小。真正的答案是 acdb它通过删除前面的 c 和 b把 a 顶到了第一位代价是 c 和 b 在后面还有一次出现机会所以不会弄丢字符。1.2 字典序最小在题目里的具体含义两个等长字符串比较字典序就是从左到右逐位比第一个不同的字符谁小谁就整体更小。放在这道题里目标可以理解成尽量让更小的字符出现在更靠前的位置。但“尽量靠前”不是无代价的。你不能直接把 a 从后面拽到最前面你要做的是把挡在 a 前面的那些字符删掉而且前提是删掉之后这些字符在后面还能找到替补。这就是整道题贪心决策的核心矛盾我想让小的字符往前顶但我不能牺牲任何字符的唯一性。生活里可以这么类比一队人按顺序排队上车有些人有多个分身站在队伍不同位置但你最后只允许每个名字保留一个人并且队伍的相对顺序不能乱。这时候如果队伍前面站了个 z而 z 在后面还有分身同时队伍后面又来了一个 a你就可以让前面的 z 下车把 a 往前提。能不能下车取决于这个 z 后面还有没有分身。1.3 一个小例子看透本质手推 s cbacdcbc。正确输出是 acdb。怎么来的索引 0 是 c它后面还有 c所以它可以被后面更小的字符替换索引 1 是 b它后面也有 b所以同样可以替换索引 2 是 a它后面没有 a 了所以它一旦出现就必须保留并且它比 c、b 都小于是把前面两个较大的字符挤掉自己站在第一位。到这里你会发现每次决定要不要让某个字符待在栈里真正要回答的问题是栈顶那个字符在这个位置后面还会不会再出现。如果会就有资格被弹出给更小的字符腾位置如果不会弹出去就再也找不回来了只能忍着。这一节的结论就是这题的本质不是“删掉重复字符”而是“在保证子序列合法、字符不丢失的前提下做字典序贪心”。理解到这一步代码其实已经呼之欲出了。2. 核心解法为什么是单调栈而不是贪心排序2.1 从“要不要弹出”到单调栈刚才那个“要不要弹出栈顶”的决策反复出现就是典型的单调栈场景。所谓单调栈简单说就是栈内元素从栈底到栈顶保持有序本题我们维持的是字典序不减也就是栈顶是当前栈内最大的字符。每遇到一个新字符 ch想把它放进栈里就先看一眼栈顶如果栈顶字符比 ch 大并且栈顶字符后面还会再出现那就把栈顶弹掉。为什么弹出因为留着这个更大的字符在更靠前的位置会让字典序变大而既然它后面还会出现说明这个位置不是非它不可删掉它更优。这个动作可以一直重复直到栈顶比 ch 小或者栈顶字符后面不再出现。你可能会问弹出一堆字符之后会不会因为栈内字符变少而丢失不会。第一个弹出条件“后面还会出现”正是为了保证它后面有替补第二个条件是栈顶大于当前字符保证每次弹出都让字符串变得更小。两个条件缺一不可。当栈顶已经比 ch 小的时候说明 ch 直接追加在后面不会破坏字典序的单调性那就直接压栈。整个过程走完栈底到栈顶的顺序就是答案。2.2 两个关键预处理的角色实现里有两种常见预处理写法本质等价。第一种是记录每个字符最后出现的位置称为 last_pos。先完整扫描一遍字符串存下每个字符最后一次出现的索引。之后遍历到位置 i判断栈顶字符 c 后面还有没有机会出现只需要看last_pos[c] i是否成立即可。第二种是用计数器维护“剩余出现次数”。每遍历一个字符就把它的计数减一判断栈顶字符后面还有没有时看cnt[stack[-1]] 0。这两种都能回答“后面还会不会出现”这个问题只是判定依据不同。我个人更推荐先写 last_pos 版本。理由有两条第一语义直白“最后一次出现的位置”本身就是为这个判定量身定做的第二不需要在遍历过程中小心翼翼地同步计数器少了一个出错点。计数器版本在题解里也很常见但新手容易在 cnt[c] 递减的时机上绕晕甚至把计数减成负数。只要判断条件写的是 0负数也不影响正确性因为负数同样意味着后面已经没有了但维护起来显然比 last_pos 版本多一层心思。2.3 三个条件拼出完整决策把上面的逻辑整理一下得到处理每个字符时的完整流程如果当前字符已经在栈中直接跳过。因为栈里已经有一个更靠前的同类字符更靠前的位置对后面的大字符来说“容错空间”更大后续所有相同字符都不可能产生更优结果。如果栈不为空且栈顶字符大于当前字符且栈顶字符在后面还会出现就循环弹出栈顶并且同步把它从“栈内集合”里移除。当前字符入栈标记为已在栈内。这里我要特别强调第 2 步里的“后面还会出现”。很多错误解法就是少了这个判断导致某个只出现一次的字符被弹出去最后结果缺字母。代码里对应的条件就是last_pos[stack[-1]] i。为什么是严格大于而不是大于等于在这道题的遍历过程中遍历到索引 i 时栈顶字符不可能是位置 i 上的字符原因在于如果那个字符在栈里第一步就直接 continue 了所以实际运行中不存在 的情况大于等于也不会触发错误。但写成严格大于在语义上更精确——“在这个位置之后还会再出现”习惯了这样的表达到了其他类似题目里也不容易写错。3. 完整实现与逐行解读3.1 Python 参考实现下面是可以用 Python 直接跑的版本。def remove_duplicate_letters(s: str) - str: # 预处理记录每个字符最后一次出现的位置 last_pos {} for i, ch in enumerate(s): last_pos[ch] i stack [] in_stack set() for i, ch in enumerate(s): # 字符已经在栈里跳过后续所有相同字符 if ch in in_stack: continue # 栈顶字符比当前字符大且以后还会出现就可以弹出 while stack and stack[-1] ch and last_pos[stack[-1]] i: in_stack.remove(stack.pop()) stack.append(ch) in_stack.add(ch) return .join(stack)变量名我做了简单化处理last_pos 记录每个字符最后一次出现的位置in_stack 负责 O(1) 判断字符是否已经在栈内。字符集如果是小写字母你也可以用布尔数组替代 set不过用 set 更通用少写一堆越界判断。3.2 逐行解释几个关键点第一个关键点是预处理循环。last_pos 的构建必须在主循环之前完成因为它要为“后面还会不会出现”提供全局信息。如果你边遍历边维护这个信息就会陷入“我需要知道未来但未来还没走到”的困境。第二个关键点是 in_stack 的 add 和 remove 必须配对。字符入栈时 add弹出时 remove。很多人写着写着只记得入栈时 add忘了弹出时 remove结果字符明明已经不在栈里了却因为集合里还残留标记而被 continue 跳过导致结果缺字符。这个坑我后面单独讲。第三个关键点是栈的顺序。最后返回.join(stack)不是stack[::-1]。栈底元素是最早确定下来的、字典序尽可能小的前缀栈顶是不断追加的后续字符。整个栈从底到顶恰好就是原字符串的一个子序列直接拼接即为答案。很多从“每日温度”之类题目过来的同学会习惯性 reverse这里千万注意。如果你用的不是 Python写 C 或 Java 时只需要把 set 换成 unordered_set / HashSet或者用一个长度为 26 的布尔数组前提是题目明确只有小写字母。其他逻辑完全一致。3.3 测试用例与输出验证我实际跑过的几组用例放在下面你可以拿自己的实现直接对照。输入输出覆盖点cbacdcbcacdb标准贪心需要弹出 c 和 b 把 a 顶到首位bcabcabc每个字符都能通过弹出得到递增顺序abcdabcd已经有序不触发任何弹出aaaaa全是重复字符只保留一个bbcaacbacb 后面不再出现时不能弹结果不是 abcabacbabc已存在的 a、b 后续出现要跳过空串边界其中 bbcaac 是很好的反直觉用例。肉眼一看好像该输出 abc但原串里 b 第一次出现在开头之后到第三个位置才出现 ab 的最后一次出现在索引 1而 a 在索引 3处理到 a 时 b 已经没有替补所以 b 必须留在第一位正确答案是 bac。这个用例能帮你快速验证是否漏写了 last_pos 判断。4. 调试复盘几个让我卡了很久的边界 case4.1 坑一弹出栈顶时忘记同步移除标记我在第一版实现里犯过一个很隐蔽的错误while 循环里 stack.pop() 执行了却没有同步执行 in_stack.remove()。在简单用例上完全正常结果到 cbacdcbc 就直接翻车。当时输出的结果是 ad而正确结果是 acdb少掉了 b 和 c。为什么我把弹出来的 c 从栈里移走了但 in_stack 里还留着 c 的痕迹。之后遍历到索引 3 的 c 时快捷判断 ch in in_stack 直接命中代码以为 c 已经在栈里于是 continue错过了让 c 重新入栈的机会。b 同理。最后栈里只剩 a 和 d。排查过程也很直接我加了一行print(fi{i}, ch{ch}, stack{stack}, in_stack{in_stack})盯着每一步的输出很快就发现弹出操作之后 in_stack 和 stack 内容不一致。修复就是在 pop 的同时移除集合标记。这类 bug 的特点是不会在简单用例上暴露因为简单用例里很少发生“弹出之后又需要重新入栈”的情况所以测试用例务必覆盖上面的 cbacdcbc。4.2 坑二少了“后面还会出现”的判断结果缺字母另一个很容易犯的错误是把弹出条件简写成while stack and stack[-1] ch没有判断last_pos[stack[-1]] i。看起来逻辑很顺——只要栈顶比我大我就弹掉让小的往前进。但这样会把一些只出现一次的字符弹出导致结果缺字母。反例我用的是 bcab。正确输出是 bca保留 b、c、a 的顺序删除最后一个 b 即可。错误版本执行到索引 2 的 a 时会把栈里的 c 弹掉因为 c 比 a 大但 c 在后面已经没有机会了接着把 b 也弹掉因为 b 比 a 大再 push a。走到索引 3 的 bpush b。最后输出 ab把 c 弄丢了。这个坑的教训很直接字典序贪心的前提是“所有字符都必须出现一次”所以“丢掉一个字符”是比“字典序不够小”严重得多的错误。做题时我习惯先把约束写在注释里每写一个删除动作就问自己一句删了之后它后面还有没有替补如果没有这个删除动作就是非法的。4.3 坑三字符集假设太死导致潜在越界LeetCode 原题一般会说明输入只包含小写字母于是很多题解直接用长度为 26 的数组存 last_pos。这没问题但如果你把代码搬到另一个“没说明字符集”的环境或者想着写一个更通用的版本还是用字典更稳妥。我自己的习惯是无论题目限不限制小写都用 dict 或者 HashMap 存 last_pos。这样遇到大写字母、数字甚至中文都不会出问题而性能损失几乎可以忽略。字符集小的情况下用数组确实快但做题时优先保证正确性和通用性真要压性能再换也不迟。4.4 小技巧用暴力对拍验证正确性因为贪心解法容易在边界上翻车我强烈建议在写完正解之后再写一个暴力版本做随机对拍。暴力版本不考虑效率只求正确枚举原字符串的所有子序列筛出恰好包含所有独特字符、且长度等于独特字符数量的那部分再取字典序最小的一个。def brute_force(s: str) - str: n len(s) target set(s) best None for mask in range(1 n): t .join(s[i] for i in range(n) if (mask i) 1) if set(t) target and len(t) len(target): if best is None or t best: best t return best or 然后随机生成小写字母组成的短字符串长度控制在 10 以内跑几百组对比 remove_duplicate_letters 和 brute_force 的结果。只要有差异就打印输入和两个输出。这个方法帮我抓出过至少两处实现问题比肉眼盯着测试用例高效得多。如果你的实现已经过了对拍基本可以放心交给评测机。5. 从3816题看一类题的通用套路5.1 单调栈的题感从哪里来很多刚开始刷题的人会觉得单调栈是个很“玄”的数据结构因为它不像排序或二分那样有固定的操作模板。刷完这道题你会意识到单调栈真正解决的是“在线决策”问题数据一个接一个到达每个新元素都可能要求前面某个元素让位让位的条件是“被让位的元素在后面还有机会”。这类题目有几个共同特征目标是一个“最小”或“最大”的排列结果决策过程中当前元素可以替换前面的元素替换的合法性通常需要某种“未来信息”来判断比如最后出现位置、剩余个数、下一个更大元素的距离。一旦你发现题目同时满足这三条就可以优先考虑单调栈而不是暴力排列或者动态规划。同一把钥匙还能开很多锁比如经典的每日温度、接雨水、柱状图中最大的矩形核心都是维护一个栈内有序的状态差别只在于弹出条件和栈里存的到底是什么。5.2 如果题目变化怎么应对这一题的标准版本是“每个字符保留一次”如果面试官改一改限制解法要跟着调整。比如字符集从 26 个小写字母变成任意 Unicode 字符last_pos 从字典改成哈希表即可思路不变。如果题目改成“删除重复字符后返回字典序最小的结果但结果最多保留 k 种不同字符”那单调栈的判定就要多一层“栈内字符种数是否达到上限”的判断解法会从纯粹的贪心变成需要配合计数和回退的复杂策略。再比如输入长度特别大字符串流式到达、无法预扫描那 last_pos 方案就不可用了需要改成边遍历边维护剩余计数的计数器版本因为“最后出现位置”依赖完整扫描。刷这种变体题的价值就在这里你掌握的不是一道题的答案而是一个决策系统换参数、换边界系统的骨架还在。5.3 实际工程里什么时候会用到这类思路不要以为单调栈只活在面试题里。我后来在清理一批多来源配置文件时就遇到了非常类似的需求多个 source 会写入同一批键值键有重复需要去重后输出一份“尽可能稳定且可读”的清单同时还要尊重一个预定义的优先级顺序。当时我第一个想到的就是单调栈的思路——用一个栈维护已选键遇到更高优先级的键时判断被压在下面的低优先级键后面还会不会出现会的话就弹出去。虽然工程里的判断条件比算法题复杂但那个“当前元素能不能替换前面元素”的框架是完全通用的。这也是为什么我一直建议刷题别只背模板把每道题背后的判断逻辑搞清楚碰到真实项目里的新场景你会比没刷过题的人更快想到方案。我个人做这题最大的收获其实是把“贪心 单调栈 未来信息预处理”这三件事焊在了一起。以前遇到“最小结果”类问题我总是本能地往排序或动态规划上靠现在会先问一句能不能用一个栈维护当前最优前缀再配合某种预处理的未来信息让更优的元素进场时把差元素换掉。这道题就是一个外科手术级别的干净案例。