LeetCode 1081. 不同字符的最小子序列

2021-12-02 HGNULB 约 11 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 1081. 不同字符的最小子序列

题意分析

要求从字符串里挑出一个子序列，它必须同时满足三件事：包含 s 中出现过的每一种字符恰好一次；保持这些字符在原串里的相对先后顺序；在所有满足前两条的方案里字典序最小。注意「子序列」意味着只能删字符不能重排，所以字符之间的顺序是被原串锁死的，我们唯一的自由度是：某个字符出现了多次时，究竟保留哪一次。

约束透露的信号很清楚。字符集只有小写字母，也就是最多 26 种，答案长度天然被压到不超过 26，这暗示可以对每种字符维护常数大小的辅助信息（比如出现位置、是否已选）。而字符串长度上限一千，虽然 $O(n^2)$ 甚至朴素枚举勉强能过，但「字典序最小」这个目标本身是典型的贪心信号：字典序比较是从左往右逐位定胜负的，前面的位只要能变小，后面付出多大代价都值得，这种"前缀优先"的性质几乎总能用一次线性扫描配一个可回退的结构解决。

边界主要有三处：字符串里全是同一个字符时，答案是单个字符；每个字符只出现一次时，答案就是原串本身，任何「优化」都不该动它；还有最容易翻车的一处，当一个较大的字符在后面不再出现时，哪怕它挡住了更小的字符，也绝对不能丢，否则结果就漏掉了这种字符，连合法性都不满足了。

解法：单调栈维护候选

核心思路

暴力做法是枚举每一种字符的保留位置组合，检查合法性后取字典序最小。字符集虽只有 26 种，但组合数是每种字符出现次数的乘积，最坏情况下呈指数爆炸，完全不可行。稍微聪明一点的做法是递归贪心：每次在「保证剩余后缀仍包含所有还没选的字符」的前提下，在可行区间里选最小的字符作为下一位，然后把区间左端推到它右边。这个做法正确但每层都要扫一遍区间，是 $O(26n)$ 到 $O(n^2)$ 的量级，而且实现时区间边界很难写对。

瓶颈在于：递归贪心每选一位都要重新扫描一次后缀，重复劳动太多。观察一下决策之间的关系会发现，答案是「边扫边可撤销地构建」的。假设我们已经处理完前缀并保留了一个候选序列，现在读到字符 c：如果候选序列的末尾字符 top 比 c 大，而且 top 在 c 之后的位置还会再次出现，那么把 top 从当前位置删掉是严格更优的——删掉后这一位由更小的 c 顶上，字典序立刻变小，而 top 这个字符本身可以在后面某次出现时补回来，合法性不受影响。反过来，如果 top 之后不再出现，或者 top 比 c 小，就必须留着：前者是合法性要求，后者动了反而变大。

这个「只在末尾撤销」的模式正是栈的语义，于是可以显式写出算法维护的不变量：任意时刻，栈内自底向上的字符构成的序列，是「仅考虑已扫描前缀、且在这个前缀的所有合法保留方案中」字典序最小的那个候选，并且栈内字符两两不同；同时布尔数组 used 与栈内容严格同步，used[x] 为真当且仅当字符 x 目前在栈里。为了判断「后面还会不会再出现」，预处理数组 last[x] 记录字符 x 在整个串里最后一次出现的下标，判断条件就是 last[top] > i。

还需要一条剪枝来保证不变量里的「两两不同」：扫描到 c 时如果 used[c] 已经为真，说明栈里已有一个 c，它所在的位置一定比当前更靠左。既然更靠左的位置字典序不劣，就直接跳过当前这个 c，什么都不做。栈的单调性由此成为一个副产品——弹栈条件是 top > c，所以栈内自底向上是严格递增的，但这只是结果，真正的依据是上面那条贪心交换论证。

解题步骤

先扫一遍字符串填 last[26]，让 last[c - 'a'] 等于字符 c 最后一次出现的下标。为什么要用「最后一次」而不是「下一次」：判断「弹掉栈顶后还能不能补回来」只需要知道它在当前位置之后是否还有任何一次出现，而最后一次出现的下标大于 i 与「之后还有出现」是等价的，这样用一个静态数组就够，不必维护动态的下一次出现位置。

准备一个 used[26] 布尔数组和一个当做栈用的 StringBuilder（Go 里是字节切片）。用 StringBuilder 而不是真正的 Stack，是因为最后要直接输出这个序列，用可变字符串省掉一次反转。

从左往右扫描每个字符 c。第一件事是判 used[idx]，为真就 continue。这一步必须放在弹栈逻辑之前：如果先进弹栈循环，栈里已有的那个 c 可能被误判处理，而且重复入栈会破坏「字符恰好一次」的约束。

接着进入弹栈循环，条件是「栈非空」且「栈顶 top > c」且「last[top] > i」。三个条件缺一不可：第一条防越界，第二条保证只有换成更小的字符才动手（相等时不动，因为相等换了没收益还会多绕一圈），第三条保证被弹掉的字符后面能补回来，这是合法性的底线。弹栈时必须同步把 used[top] = false，否则 used 与栈失同步，这个字符后面再出现时会被第一步的 continue 拦掉，答案就缺字符了。

弹到不能再弹后把 c 压栈并置 used[idx] = true。此时不变量重新成立：栈仍严格递增、字符仍两两不同、used 仍与栈同步。

扫描结束后栈里的内容就是答案，直接转成字符串返回，不需要任何收尾处理——因为不变量对「已扫描前缀」始终成立，扫完全串时前缀就是全串。

以 s = "cbacdcbc" 走一遍。预处理得到 last['a'] = 2、last['b'] = 6、last['c'] = 7、last['d'] = 4。i=0 读到 c，栈空，直接压入，栈为 "c"。i=1 读到 b，used[b] 为假，栈顶 c > b 且 last[c] = 7 > 1，说明 c 后面还会出现，弹掉它并把 used[c] 置假，栈空了，压入 b，栈为 "b"。i=2 读到 a，栈顶 b > a 且 last[b] = 6 > 2，弹掉 b，栈空，压入 a，栈为 "a"。i=3 读到 c，used[c] 此前已被置回假，栈顶 a < c 不满足弹栈条件，直接压入，栈为 "ac"。i=4 读到 d，栈顶 c < d，压入，栈为 "acd"。i=5 又读到 c，used[c] 为真，直接跳过——保留更靠左的那个 c 一定不劣。i=6 读到 b，栈顶 d > b 看似该弹，但 last[d] = 4 并不大于 6，说明 d 在后面再也不出现了，弹掉就永远补不回来，于是循环立刻退出，把 b 压入，栈为 "acdb"。i=7 读到 c，used[c] 为真，跳过。扫描结束，答案 "acdb"。可以对比一下："acdb" 确实比同样合法的 "acbd" 大，但 "acbd" 根本不是子序列（原串里 b 之后没有 d），这正是第三个弹栈条件在起作用的地方。

代码实现

class Solution {
    // 维护一个递增栈，保证字典序最小且字符唯一。
    public String smallestSubsequence(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        boolean[] used = new boolean[26];
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'a';

            if (used[idx]) {
                continue;
            }

            while (stack.length() > 0) {
                char top = stack.charAt(stack.length() - 1);
                if (top > c && last[top - 'a'] > i) {
                    used[top - 'a'] = false;
                    stack.deleteCharAt(stack.length() - 1);
                } else {
                    break;
                }
            }

            stack.append(c);
            used[idx] = true;
        }

        return stack.toString();
    }
}

func smallestSubsequence(s string) string {
    // 维护一个递增栈，保证字典序最小且字符唯一。
    last := make([]int, 26)
    for i := 0; i < len(s); i++ {
        last[s[i]-'a'] = i
    }

    used := make([]bool, 26)
    stack := make([]byte, 0)

    for i := 0; i < len(s); i++ {
        c := s[i]
        idx := c - 'a'
        if used[idx] {
            continue
        }

        for len(stack) > 0 {
            top := stack[len(stack)-1]
            if top > c && last[top-'a'] > i {
                used[top-'a'] = false
                stack = stack[:len(stack)-1]
            } else {
                break
            }
        }

        stack = append(stack, c)
        used[idx] = true
    }

    return string(stack)
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为字符串长度。预处理扫一遍是 $O(n)$；主循环每个字符至多入栈一次、出栈一次，弹栈循环的总执行次数被入栈总次数上界控制，所以摊还下来仍是线性，而不是嵌套循环看上去的平方。

空间复杂度：$O(1)$，凭的是 last 和 used 都固定为 26 个槽位，栈里字符两两不同所以深度也不超过 26，全都与 $n$ 无关，只有作为返回值的字符串本身随字符集大小变化。

关键点总结

「字典序最小」几乎总是意味着贪心加可撤销结构：字典序从左往右定胜负，所以只要能让靠前的位变小，就应该立刻动手；而「动手之后会不会失去合法性」这个反问，决定了撤销的条件长什么样。

弹栈条件要拆成「收益」和「可行性」两半来写。top > c 是收益（换成更小的字符字典序变小），last[top] > i 是可行性（被弹掉的字符还能补回来）。任何一个单调栈题目卡壳时，都可以回到这两问上重新推条件。

辅助的 used 数组必须与栈严格同步维护，弹栈时置假、压栈时置真。这类「两份状态互为镜像」的写法，是面试里最容易被追问的实现细节，主动说出「我在弹栈时把 used 复位，保证两者一致」会显得实现功底扎实。

时间复杂度不能看到 while 套 for 就说 $O(n^2)$。要用摊还分析说明「每个元素至多进栈出栈各一次」，这是单调栈类题目在面试中必须能讲清的一点。

面试视角上，这题和 316. 去除重复字母是完全相同的题（LeetCode 上是两个题号的同一道题）。遇到时可以直接指出这一点，然后强调本题的正确性依赖的是交换论证而非「单调栈模板」，因为模板背错方向就会把不该弹的字符弹掉。

预处理选「最后一次出现位置」而不是「剩余计数」或「下一次出现位置」，是因为判断条件只需要一个布尔性质，静态数组是最省事的实现；如果改用计数数组则每步都要递减，多一处容易写错的状态。

易错点总结

错误写法：把 used[idx] 的判断放在弹栈循环之后。用例 "cbacdcbc" 在 i=5 读到重复的 c 时会先跑弹栈逻辑，把栈顶的 d 拿去和 c 比较，随后又把 c 重复压栈，输出里出现两个 c，直接违反「每种字符恰好一次」。

错误写法：弹栈时忘记写 used[top - 'a'] = false。用例 "cbacdcbc" 在 i=1 弹掉 c 后，used[c] 仍为真，i=3 的 c 会被 continue 跳过，i=7 的同样被跳过，最终答案变成 "adb"，少了字符 c。

错误写法：弹栈条件漏掉 last[top - 'a'] > i，写成只要 top > c 就弹。用例 "cbacdcbc" 在 i=6 会把 d 弹掉（此后 d 再不出现），输出 "acb"，缺少 d，答案不合法。

错误写法：把弹栈条件里的 > 写成 >=，即 top >= c 时也弹。用例 "aa"，第二个 a 本会被 used 拦下不会触发；但配合上一条 used 判断位置写反的错误时，"abab" 会反复弹入同一字符，栈内出现重复字符且循环行为不可控。

错误写法：last 数组用「第一次出现的下标」填充，即写成 if (last[idx] == 0) last[idx] = i;。用例 "cbacdcbc" 中 last[c] 会变成 0，i=1 时 last[c] > 1 不成立，c 不会被弹掉，输出 "cabd" 这类前缀更大的结果。

错误写法：预处理和主扫描写在同一个循环里，边扫边填 last。用例 "cbacdcbc" 在 i=1 时 last[c] 只记录到 0，弹栈判断拿不到未来信息，等价于上一条的后果，答案偏大。

错误写法：弹栈循环写成 if 而不是 while。用例 "cba"，i=2 读到 a 时只弹掉一个 b 就停手，栈变成 "ca"，最终输出 "ca"，而正确答案是 "abc" 的子序列形式 "a" 之后接不上，实际输出 "ca" 字典序明显大于正确的 "a" 开头结果。

错误写法：用 s.indexOf(c, i + 1) != -1 代替 last 数组来判断后面是否还有该字符。用例是长度接近上限且字符高度重复的串，每次判断都要重新扫后缀，整体退化到 $O(n^2)$，虽然本题数据量小能过，但面试里会被直接指出复杂度不达标。

错误写法：最后返回时把栈反转再输出。用例 "cbacdcbc" 会输出 "bdca"，顺序完全颠倒——这个栈是「自底向上即答案顺序」的，和那些需要反转的进位模拟题不同。

错误写法：为了「去重」先用 LinkedHashSet 之类的结构把重复字符过滤掉再排序。用例 "cbacdcbc" 会得到排序后的 "abcd"，它根本不是原串的子序列（a 之后没有 b），合法性被破坏，而这类库函数捷径正好绕开了本题的考点。

相似题目

题目	难度	考察点
42. 接雨水	困难	弹栈时按「层」结算凹槽体积，需要左右两侧边界同时参与
84. 柱状图中最大的矩形	困难	栈里存下标，弹栈瞬间才能确定矩形的左右边界
316. 去除重复字母	中等	与本题完全同题，可用来交叉验证自己的实现
321. 拼接最大数	困难	单调栈只是子过程，外层还要枚举两数组的取数分配并归并
394. 字符串解码	中等	栈保存的是嵌套上下文而非单调序列，考察括号配对的还原
402. 移掉 K 位数字	中等	弹栈次数由固定额度 k 限制，而不是「后面还会出现」
496. 下一个更大元素 I	简单	单调栈结果先存哈希表，再做跨数组的下标映射
503. 下一个更大元素 II	中等	数组成环，靠扫描两遍或取模下标模拟环形
739. 每日温度	中等	栈内存下标，结算的是位置差而不是元素值
1249. 移除无效的括号	中等	栈记录的是待删除下标，没有单调性，只做配对
1673. 找出最具竞争力的子序列	中等	结果长度固定为 k，弹栈可行性由「剩余元素够不够」决定