栈神：绝版不能踢，这是江湖规矩不是抽卡游戏

那天凌晨，我正对着 LeetCode 1081 发呆，眼皮一沉，直接栽进键盘缝里。

再睁眼时，面前站着一排字母，领头的那个 c 戴着墨镜，叼着牙签：“喂，你就是那个写了三千行 if-else 的菜鸡？”

我还没来得及反驳，它掏出一张卷轴：“给你个任务——把我们这串字符cbacdcbc变成一个包含所有不同字母、每个字母只出现一次、且字典序最小的队伍。搞不定的话，我就把你的代码直接推到生产环境去。”

我当场腿软，差点给它磕了一个——正发懵呢，旁边飘来一个幽灵老头，胡子长得像条拖尾的 log，开口自带混响：“年轻人，复习一下单调栈试试？”

我抬头一看，这老头浑身散发着“我年轻时写过汇编”的气场，连忙点头如捣蒜。

他捋了捋胡子，自称栈神：“江湖规矩就一条——如果栈顶那哥们比你大，而且它以后还能再登场，你就一脚把它踹飞。否则，乖乖往后排。” 说完还丢过来一张发光的羊皮纸：“这是‘最后出现位置表’，每个字母这辈子最后一秀全记在上面。别弄丢了，这玩意儿比你的 README.md 值钱。”

我接过一看——c:7 b:6 a:2 d:4，确实标了每个字母最后一次出场的位置。

“这不就是个字典嘛，我也会写。”我小声嘀咕。栈神白了我一眼：“小子，这叫预处理，O(n)扫描一次搞定。”

我不敢顶嘴，赶紧把羊皮纸揣进兜里，又摸出一个空栈（list），再掏出一个小本本记已入队的字母（set）。万事俱备，开工。

第一个 c 大摇大摆地进栈，栈：[c]，小本本：{c}。 第二个 b 来了，一看栈顶是 c，立马叫嚣：“我 b 比 c 小，按字典序我应该站它前面！你那张破纸上写了 c 以后还有戏（位置 7），赶紧让它滚蛋！” 我一听有理，踹飞 c，迎进 b，栈：[b]，小本本：{b}。 a 来了，同样套路：比 b 小，b 最后亮相在 6，还能再见，踢 b 收 a。栈：[a]，小本本：{a}。 后面 c 又来——就刚被踹飞那个，一看栈顶是 a，立刻认怂，乖乖排队。栈：[a, c]，小本本：{a, c}。 第五个 d 比 c 大，也老实排队。栈：[a, c, d]，小本本：{a, c, d}。 接着又来个 c，我瞟了一眼小本本：“你已经入编了，别刷存在感。” 它狡辩：“我是另一个 c！” “管你是 c 还是 c++，重复就闪边。” 正顺利着，第七个字母 b 又杀回来了。它瞅着栈顶 d，嚷嚷：“我比 d 小，插队！” 我正想踹 d，栈神那句“绝版不能动” 突然劈进脑子。我赶紧翻开羊皮纸：d 的最后出场——位置4 。而现在，已经是位置 6 了！现在踹掉 d 就永远少一种字母，任务直接崩盘。 我冷汗当场就下来了，一把按住想冲上去打架的 b：“兄弟，d是绝版皮肤，踢了就再也抽不到了，后面排着去。” b 一脸憋屈，但为了组队成功，只能钻进队尾。栈：[a, c, d, b]，小本本：{a, c, d, b}。 最后一个 c 又想来蹭镜头，我小本本一翻，直接在它脸上画了个叉：“重复角色，别来骗时长。”

大幕落下，最终队伍亮相：a c d b，连起来就是 "acdb"。

墨镜 c 摘了墨镜，瞳孔地震：“我去，还真是字典序最小，每种字母只露脸一次……你小子连 sudo apt-get 都打错，算法居然这么清醒？”

我故作淡定：“这招叫用最后出现位置做贪心剪枝的单调栈。每个字母最多入栈一次、出栈一次，O(n) 复杂度，别说你们这破队伍只有8个字符，就是长度拉到 1000，我也只当是热身。”

正想仰天长笑，闹钟炸了。我满脸键盘印子惊醒，屏幕还在闪烁：

def smallestSubsequence(s: str) -> str:
    oracle = {c: i for i, c in enumerate(s)}  # 羊皮纸
    magic_stack = []
    already_in_team = set()
    for i, c in enumerate(s):
        if c in already_in_team:
            continue
        while magic_stack and magic_stack[-1] > c and oracle[magic_stack[-1]] > i:
            already_in_team.remove(magic_stack.pop())
        magic_stack.append(c)
        already_in_team.add(c)
    return "".join(magic_stack)

我揉揉眼睛，这些变量名是什么鬼，栈神埋的彩蛋吗？还没等我改，同事的 Slack 消息就弹了过来：“你那个 oracle 是去古希腊写代码了？下次 commit 之前能不能切回人话？”

我关掉聊天框，端起咖啡。下次再梦到字母，我要带它们跳跳表，卷死字典树。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。