返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
示例 1：
**输入：**s = "bcabc"
**输出：**"abc"
示例 2：
**输入：**s = "cbacdcbc"
**输出：**"acdb"
提示：
1 <= s.length <= 1000s 由小写英文字母组成
注意： 该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同
📺 视频题解
📖 文字题解
方法一：贪心 + 单调栈
思路与算法
首先考虑一个简单的问题：给定一个字符串 s，如何去掉其中的一个字符 ch，使得得到的字符串字典序最小呢？答案是：找出最小的满足 s[i]>s[i+1] 的下标 i，并去除字符 s[i]。为了叙述方便，下文中称这样的字符为「关键字符」。
在理解这一点之后，就可以着手本题了。一个直观的思路是：我们在字符串 s 中找到「关键字符」，去除它，然后不断进行这样的循环。但是这种朴素的解法会创建大量的中间字符串，我们有必要寻找一种更优的方法。
我们从前向后扫描原字符串。每扫描到一个位置，我们就尽可能地处理所有的「关键字符」。假定在扫描位置 s[i-1] 之前的所有「关键字符」都已经被去除完毕，在扫描字符 s[i] 时，新出现的「关键字符」只可能出现在 s[i] 或者其后面的位置。
于是，我们使用单调栈来维护去除「关键字符」后得到的字符串，单调栈满足栈底到栈顶的字符递增。如果栈顶字符大于当前字符 s[i]，说明栈顶字符为「关键字符」，故应当被去除。去除后，新的栈顶字符就与 s[i] 相邻了，我们继续比较新的栈顶字符与 s[i] 的大小。重复上述操作，直到栈为空或者栈顶字符不大于 s[i]。
我们还遗漏了一个要求：原字符串 s 中的每个字符都需要出现在新字符串中，且只能出现一次。为了让新字符串满足该要求，之前讨论的算法需要进行以下两点的更改。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
string smallestSubsequence(string s) {
vector<int> vis(26), num(26);
for (char ch : s) {
num[ch - 'a']++;
}
string stk;
for (char ch : s) {
if (!vis[ch - 'a']) {
while (!stk.empty() && stk.back() > ch) {
if (num[stk.back() - 'a'] > 0) {
vis[stk.back() - 'a'] = 0;
stk.pop_back();
} else {
break;
}
}
vis[ch - 'a'] = 1;
stk.push_back(ch);
}
num[ch - 'a'] -= 1;
}
return stk;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public String smallestSubsequence(String s) {
boolean[] vis = new boolean[26];
int[] num = new int[26];
for (int i = 0; i < s.length(); i++) {
num[s.charAt(i) - 'a']++;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!vis[ch - 'a']) {
while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
vis[sb.charAt(sb.length() - 1) - 'a'] = false;
sb.deleteCharAt(sb.length() - 1);
} else {
break;
}
}
vis[ch - 'a'] = true;
sb.append(ch);
}
num[ch - 'a'] -= 1;
}
return sb.toString();
}
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| var smallestSubsequence = function(s) {
const vis = new Array(26).fill(0);
const num = _.countBy(s);
const sb = new Array();
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (!vis[ch.charCodeAt() - 'a'.charCodeAt()]) {
while (sb.length > 0 && sb[sb.length - 1] > ch) {
if (num[sb[sb.length - 1]] > 0) {
vis[sb[sb.length - 1].charCodeAt() - 'a'.charCodeAt()] = 0;
sb.pop();
} else {
break;
}
}
vis[ch.charCodeAt() - 'a'.charCodeAt()] = 1;
sb.push(ch);
}
num[ch]--;
}
return sb.join('');
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func smallestSubsequence(s string) string {
left := [26]int{}
for _, ch := range s {
left[ch-'a']++
}
stack := []byte{}
inStack := [26]bool{}
for i := range s {
ch := s[i]
if !inStack[ch-'a'] {
for len(stack) > 0 && ch < stack[len(stack)-1] {
last := stack[len(stack)-1] - 'a'
if left[last] == 0 {
break
}
stack = stack[:len(stack)-1]
inStack[last] = false
}
stack = append(stack, ch)
inStack[ch-'a'] = true
}
left[ch-'a']--
}
return string(stack)
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| char* smallestSubsequence(char* s) {
int vis[26], num[26];
memset(vis, 0, sizeof(vis));
memset(num, 0, sizeof(num));
int n = strlen(s);
for (int i = 0; i < n; i++) {
num[s[i] - 'a']++;
}
char* stk = malloc(sizeof(char) * 27);
int stkTop = 0;
for (int i = 0; i < n; i++) {
if (!vis[s[i] - 'a']) {
while (stkTop > 0 && stk[stkTop - 1] > s[i]) {
if (num[stk[stkTop - 1] - 'a'] > 0) {
vis[stk[--stkTop] - 'a'] = 0;
} else {
break;
}
}
vis[s[i] - 'a'] = 1;
stk[stkTop++] = s[i];
}
num[s[i] - 'a'] -= 1;
}
stk[stkTop] = '\0';
return stk;
}
|
复杂度分析
