§1

题目描述

子序列指的是按原顺序、可跳着取字符拼成的串(不能打乱顺序)。要求:① 把 s 里每种不同字符都包含进来 ② 每种只留一个 ③ 在满足前两条的所有结果里,选字典序最小的那个。字典序就是像查字典那样从左往右比,越靠前的位置字母越小越好。

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

输入 = 本节演示 s = "cbacdcbc"　输出 = "acdb"

§2

思路解析动画文字版

记牢三句话:已在栈里就跳过;栈顶更大且后面还有就弹;弹不动了再入栈。判「后面还有」靠 last 表。下面每一帧都在套这套规则。

总览 · 先记下每种字符最后出现的位置：上面一排是要扫描的字符串 "cbacdcbc"。开扫之前先做件准备工作:记下每种字符最后一次出现在哪。c 最后在第 7 位,b 在第 6 位,a 在第 2 位,d 在第 4 位。这张 last 表后面用来判断「某个字符后面还会不会再出现」。栈一开始是空的,从最左边第一个字符开始扫。

读第 0 个 · c：扫到第 0 位的 c。现在栈是空的,没有谁好比较,也没法弹,那就直接把 c 放进栈,作为答案的开头候选。

入栈 · c：栈已经空了,没什么可弹的,把 c 压进栈,记进「已收录」。现在栈里是 c。继续往后扫。

读第 1 个 · b：扫到第 1 位的 b。先看一眼栈顶是 c。接下来要判断:能不能把栈顶 c 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 b 大,而且栈顶这个字符后面还得有机会再出现。

弹栈 · 移除 c：检查栈顶 c:第一关,c 比 b 大,排在前面会让字典序变大,不划算。第二关,c 的 last 是 7,比现在的位置 1 大,说明 c 后面还会再出现,现在弹掉它一点不亏,以后还能补回来。两关都过,把 c 弹出栈,顺手把它从「已收录」里去掉。

入栈 · b：栈已经空了,没什么可弹的,把 b 压进栈,记进「已收录」。现在栈里是 b。继续往后扫。

读第 2 个 · a：扫到第 2 位的 a。先看一眼栈顶是 b。接下来要判断:能不能把栈顶 b 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 a 大,而且栈顶这个字符后面还得有机会再出现。

弹栈 · 移除 b：检查栈顶 b:第一关,b 比 a 大,排在前面会让字典序变大,不划算。第二关,b 的 last 是 6,比现在的位置 2 大,说明 b 后面还会再出现,现在弹掉它一点不亏,以后还能补回来。两关都过,把 b 弹出栈,顺手把它从「已收录」里去掉。

入栈 · a：栈已经空了,没什么可弹的,把 a 压进栈,记进「已收录」。现在栈里是 a。继续往后扫。

读第 3 个 · c：扫到第 3 位的 c。先看一眼栈顶是 a。接下来要判断:能不能把栈顶 a 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 c 大,而且栈顶这个字符后面还得有机会再出现。

考察栈顶 · a 留下：再看栈顶 a:它比 c 小。栈顶更小,本来就排在前面更划算,弹掉反而让字典序变大,所以不弹。弹栈第一关就没过,停手。

入栈 · c：弹不动了,就把 c 压进栈,记进「已收录」。现在栈从底到顶是 a c。继续扫下一个字符。

读第 4 个 · d：扫到第 4 位的 d。先看一眼栈顶是 c。接下来要判断:能不能把栈顶 c 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 d 大,而且栈顶这个字符后面还得有机会再出现。

考察栈顶 · c 留下：再看栈顶 c:它比 d 小。栈顶更小,本来就排在前面更划算,弹掉反而让字典序变大,所以不弹。弹栈第一关就没过,停手。

入栈 · d：弹不动了,就把 d 压进栈,记进「已收录」。现在栈从底到顶是 a c d。继续扫下一个字符。

读第 5 个 · c 已收录：扫到第 5 位的 c。它已经在栈里了,说明这种字符早就收进答案了。题目要求每种字符只留一个,所以这里什么都不做,直接跳过,看下一个。

读第 6 个 · b：扫到第 6 位的 b。先看一眼栈顶是 d。接下来要判断:能不能把栈顶 d 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 b 大,而且栈顶这个字符后面还得有机会再出现。

考察栈顶 · d 留下：再看栈顶 d:它确实比 b 大,可第二关没过。d 的 last 是 4,没有大于现在的位置 6,说明 d 是最后一次露面,后面再也碰不到了。这时候要是弹掉它,答案里就永远缺这种字符,所以只能把 d 留着,不弹。

入栈 · b：弹不动了,就把 b 压进栈,记进「已收录」。现在栈从底到顶是 a c d b。继续扫下一个字符。

读第 7 个 · c 已收录：扫到第 7 位的 c。它已经在栈里了,说明这种字符早就收进答案了。题目要求每种字符只留一个,所以这里什么都不做,直接跳过,看下一个。

完成 · 答案 "acdb"：8 个字符全扫完了,栈从底到顶依次是 a、c、d、b。把它们顺着拼起来就是 "acdb"。可以核对一下:a、c、d、b 四种字符各出现一次,正好覆盖了原串里所有不同字符,而且这是能排出的字典序最小的那一种,答案 "acdb" 成立。

边界先想清:全相同只留一个、已经有序的原样输出、单字符就是它本身。

面试重点:last 保证「弹了能补回来」、均摊每字符进出栈各一次所以是线性、本题等同 316。

§3

参考代码

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution:    def smallestSubsequence(self, s: str) -> str:        last = {c: i for i, c in enumerate(s)}        stk = []        vis = set()        for i, c in enumerate(s):            if c in vis:                continue            while stk and stk[-1] > c and last[stk[-1]] > i:                vis.remove(stk.pop())            stk.append(c)            vis.add(c)        return "".join(stk)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n)，n 为字符串长度。先扫一遍记 last,再扫一遍维护栈;每个字符最多入栈一次、出栈一次,均摊下来还是线性
空间：O(C)，C 是字符集大小(小写字母 26)。栈、vis、last 都不超过 26 个,与 n 无关,可视作常数级额外空间

§5

易错点

✗ 错误写法：弹栈只判「栈顶比当前字符大」就弹

✓ 正确写法：还要判「栈顶后面还会再出现」(last 大于当前位置)才能弹

若栈顶后面不再出现,弹掉就永远丢了这种字符,结果会缺字符

✗ 错误写法：遇到已在栈里的字符还重复入栈

✓ 正确写法：用 vis 判重,已收录的直接跳过

题目要求每种字符只留一个,重复入栈会让同一字符出现多次

✗ 错误写法：把「字典序最小」当成「直接排序」

✓ 正确写法：必须用栈按原顺序贪心,不能打乱

子序列必须保持原相对顺序,排序会破坏可行性,得到非法结果

面试追问把动画讲成自己的话

追问为什么用「最后出现位置」就能保证不丢字符?

弹栈的本质是「先放走一个大字符,换个更小的排前面,大的以后再补」。能补的前提是这个大字符后面还会出现。last 记录的就是每种字符最后一次出现的下标,只要它大于当前位置 i,就说明后面还有这个字符,弹掉它是安全的。反过来,如果 last 不大于 i,这就是它最后一次露面,弹了就再也补不回来,所以必须留下。

追问时间复杂度为什么是 O(n) 而不是 O(n 方)?

虽然外层有循环、内层还有个 while 弹栈,看着像两层,但每个字符一生中最多被压入栈一次、弹出栈一次。所有弹栈操作加起来不会超过字符总数,所以内层 while 的总执行次数是均摊 O(n)。加上预处理 last 的一遍扫描,整体还是线性。

追问这题和 316 题去除重复字母是什么关系?

完全是同一道题,只是题号和叙述不同。316 叫「去除重复字母」,1081 叫「不同字符的最小子序列」,要求和解法一模一样:都是单调栈加贪心、用 last 或剩余计数判断后面还有没有。会了一道,另一道直接套。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 栈套路 34/49

有效括号的嵌套深度

LeetCode 1111 · 中等 · 沿着栈套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def smallestSubsequence(self, s: str) -> str: last = {c: i for i, c in enumerate(s)} stk = [] vis = set() for i, c in enumerate(s): if c in vis: continue while stk and stk[-1] > c and last[stk[-1]] > i: vis.remove(stk.pop()) stk.append(c) vis.add(c) return "".join(stk)