不同字符的最小子序列 图解题解

这道题到底在问什么

输入

s = "bcabc"

输出

"abc"

输入

本节演示 s = "cbacdcbc"

输出

"acdb"

最优解：一步一步想明白

1. 3记牢三句话:已在栈里就跳过;栈顶更大且后面还有就弹;弹不动了再入栈。判「后面还有」靠 last 表。下面每一帧都在套这套规则。
2. 4上面一排是要扫描的字符串 "cbacdcbc"。开扫之前先做件准备工作:记下每种字符最后一次出现在哪。c 最后在第 7 位,b 在第 6 位,a 在第 2 位,d 在第 4 位。这张 last 表后面用来判断「某个字符后面还会不会再出现」。栈一开始是空的,从最左边第一个字符开始扫。
3. 5扫到第 0 位的 c。现在栈是空的,没有谁好比较,也没法弹,那就直接把 c 放进栈,作为答案的开头候选。
4. 6栈已经空了,没什么可弹的,把 c 压进栈,记进「已收录」。现在栈里是 c。继续往后扫。
5. 7扫到第 1 位的 b。先看一眼栈顶是 c。接下来要判断:能不能把栈顶 c 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 b 大,而且栈顶这个字符后面还得有机会再出现。
6. 8检查栈顶 c:第一关,c 比 b 大,排在前面会让字典序变大,不划算。第二关,c 的 last 是 7,比现在的位置 1 大,说明 c 后面还会再出现,现在弹掉它一点不亏,以后还能补回来。两关都过,把 c 弹出栈,顺手把它从「已收录」里去掉。
7. 9栈已经空了,没什么可弹的,把 b 压进栈,记进「已收录」。现在栈里是 b。继续往后扫。
8. 10扫到第 2 位的 a。先看一眼栈顶是 b。接下来要判断:能不能把栈顶 b 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 a 大,而且栈顶这个字符后面还得有机会再出现。
9. 11检查栈顶 b:第一关,b 比 a 大,排在前面会让字典序变大,不划算。第二关,b 的 last 是 6,比现在的位置 2 大,说明 b 后面还会再出现,现在弹掉它一点不亏,以后还能补回来。两关都过,把 b 弹出栈,顺手把它从「已收录」里去掉。
10. 12栈已经空了,没什么可弹的,把 a 压进栈,记进「已收录」。现在栈里是 a。继续往后扫。
11. 13扫到第 3 位的 c。先看一眼栈顶是 a。接下来要判断:能不能把栈顶 a 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 c 大,而且栈顶这个字符后面还得有机会再出现。
12. 14再看栈顶 a:它比 c 小。栈顶更小,本来就排在前面更划算,弹掉反而让字典序变大,所以不弹。弹栈第一关就没过,停手。
13. 15弹不动了,就把 c 压进栈,记进「已收录」。现在栈从底到顶是 a c。继续扫下一个字符。
14. 16扫到第 4 位的 d。先看一眼栈顶是 c。接下来要判断:能不能把栈顶 c 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 d 大,而且栈顶这个字符后面还得有机会再出现。
15. 17再看栈顶 c:它比 d 小。栈顶更小,本来就排在前面更划算,弹掉反而让字典序变大,所以不弹。弹栈第一关就没过,停手。
16. 18弹不动了,就把 d 压进栈,记进「已收录」。现在栈从底到顶是 a c d。继续扫下一个字符。
17. 19扫到第 5 位的 c。它已经在栈里了,说明这种字符早就收进答案了。题目要求每种字符只留一个,所以这里什么都不做,直接跳过,看下一个。
18. 20扫到第 6 位的 b。先看一眼栈顶是 d。接下来要判断:能不能把栈顶 d 弹掉,好让更小的字符往前排。判断分两关:栈顶要比 b 大,而且栈顶这个字符后面还得有机会再出现。
19. 21再看栈顶 d:它确实比 b 大,可第二关没过。d 的 last 是 4,没有大于现在的位置 6,说明 d 是最后一次露面,后面再也碰不到了。这时候要是弹掉它,答案里就永远缺这种字符,所以只能把 d 留着,不弹。
20. 22弹不动了,就把 b 压进栈,记进「已收录」。现在栈从底到顶是 a c d b。继续扫下一个字符。
21. 23扫到第 7 位的 c。它已经在栈里了,说明这种字符早就收进答案了。题目要求每种字符只留一个,所以这里什么都不做,直接跳过,看下一个。
22. 248 个字符全扫完了,栈从底到顶依次是 a、c、d、b。把它们顺着拼起来就是 "acdb"。可以核对一下:a、c、d、b 四种字符各出现一次,正好覆盖了原串里所有不同字符,而且这是能排出的字典序最小的那一种,答案 "acdb" 成立。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    string smallestSubsequence(string s) {
        int n = s.size();
        int last[26] = {0};
        for (int i = 0; i < n; ++i) {
            last[s[i] - 'a'] = i;
        }
        string ans;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if ((mask >> (c - 'a')) & 1) {
                continue;
            }
            while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) {
                mask ^= 1 << (ans.back() - 'a');
                ans.pop_back();
            }
            ans.push_back(c);
            mask |= 1 << (c - 'a');
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public String smallestSubsequence(String text) {
        int[] cnt = new int[26];
        for (char c : text.toCharArray()) {
            ++cnt[c - 'a'];
        }
        boolean[] vis = new boolean[26];
        char[] cs = new char[text.length()];
        int top = -1;
        for (char c : text.toCharArray()) {
            --cnt[c - 'a'];
            if (!vis[c - 'a']) {
                while (top >= 0 && c < cs[top] && cnt[cs[top] - 'a'] > 0) {
                    vis[cs[top--] - 'a'] = false;
                }
                cs[++top] = c;
                vis[c - 'a'] = true;
            }
        }
        return String.valueOf(cs, 0, top + 1);
    }
}

复杂度

面试官可能追问