去除重复字母

字母种类一多，排法就爆炸式增长，根本枚举不过来。我们需要一个一趟扫完就能定下顺序的聪明办法。

关键两个条件缺一不可：① 栈顶比当前大(留着它会让串更大) ② 栈顶后面还会出现(弹了不亏，能补回)。两条都满足才敢弹。

下面演示串 cbacdcbc(下标 0~7)。先记住这张最后出现表：c 最后在 7、b 在 6、a 在 2、d 在 4。盯住栈怎么涨、怎么「反悔」。

起步 · 栈为空：上面是输入流 cbacdcbc，下面是空栈。我们额外用一个集合记「栈里已经有哪些字母」，已在栈里的字母直接跳过(因为只能留一个)。

i=0 看 c · 栈空无需比较：指针落在第一个 c(下标 0)。此刻栈还是空的，没有栈顶可比较，弹栈条件直接跳过，进入压栈。

i=0 压 c：把 c 压栈，栈变 [c]。

i=1 看 b · 比较栈顶 c：来了 b。栈顶 c 比 b 大，而且 c 的最后位置是 7、在 1 后面还会出现——两条都满足，c 可以先弹掉，把更小的 b 提前。

i=1 弹 c：弹掉 c，栈空了。不亏——c 在下标 3、5、7 还会回来，到时再压。这一步就是单调栈的「反悔」。

i=1 压 b：弹完后栈空，把 b 压栈，栈变 [b]。现在结果开头是更小的 b 而不是 c 了。

i=2 看 a · 比较栈顶 b：来了 a。栈顶 b 比 a 大，且 b 最后在 6、在 2 后面还会出现——可以弹，让最小的 a 排到最前。

i=2 弹 b：弹掉 b，栈又空了。b 在下标 6 还会回来，不怕丢。

i=2 压 a：把 a 压栈，栈变 [a]。注意 a 最后就出现在这里(下标 2)，往后永远不会再来——所以 a 一旦进栈，谁都别想再把它弹走。

i=3 看 c · 比较栈顶 a：来了 c。栈顶是 a，a 比 c 小，留着 a 不会让串变大，不弹。直接进入压栈。

i=3 压 c：c 不在栈里，压栈，栈变 [a, c]。这个 c 就是前面弹掉的 c「补回来」了。

i=4 看 d · 比较栈顶 c：来了 d。栈顶 c 比 d 小，不该弹，留着。准备压 d。

i=4 压 d：d 不在栈里，压栈，栈涨到 [a, c, d]，目前是升序、很「整齐」。

i=5 看 c · 已在栈里：又来一个 c，但 c 已经在栈里了。每个字母只能留一个，所以直接跳过，栈不动。

i=6 看 b · 比较栈顶 d：来了 b。栈顶 d 确实比 b 大，但 d 最后只出现在下标 4，已经在 6 前面了——弹了 d 就永远补不回来！第二个条件不满足，不能弹。

i=6 压 b：既然 d 不能弹，b 只好压在后面，栈变 [a, c, d, b]。这就是为什么结果末尾是 b——它没法再往前提了。

i=7 看 c · 已在栈里：最后一个 c，栈里已经有 c，跳过，栈保持 [a, c, d, b]。

扫描结束：串走完了，栈从底到顶拼起来就是答案 acdb。每个字母只留一个、整串字典序最小，全靠那两条弹栈条件一趟扫出来。

整条 cbacdcbc 只从左扫到右一遍，没有任何回头——这就是单调栈把指数级压到 O(n) 的威力。

凡是「要让结果字典序/数值最优、且元素以后还可能再遇到」的题，第一反应就该想到单调栈 + 反悔。

雷区实演 · 错误地只看大小：如果只看「d > b」就弹掉 d(不查它最后位置)，栈会变成 [a, c, b]。

雷区实演 · d 永久丢失：可 d 在下标 6 之后再也不出现，弹了就补不回来，最终错得到 acb(少了 d)。正确做法必须查 last[d]=4 不能弹 d。

边界实演 · 已全在栈 abc：像 abcabc：前三个 a,b,c 升序压栈，后三个 a,b,c 全都已在栈里被跳过，结果就是 abc。没有任何弹栈。

边界三连：先想没重复(只压)、有大量重复(跳过)、最小规模(单字符)三种，代码就稳了。

面试追问：把「两条弹栈条件为何缺一不可」讲清楚，是这题面试的得分点。