题目描述
返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
注：子序列 是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组。
示例 1：
输入：s = “bcabc” 输出：“abc”
示例 2：
输入：s = “cbacdcbc” 输出：“acdb”
提示：
- 1 <= s.length <= 1000
- s 由小写英文字母组成
苯人思路
贪心 + 递归
class Solution {
public:
string search(vector<vector<int>>& indice, string answer, int N[],
int number, int front) {
bool flag1 = false;
bool flag2 = false;
// 按字典序遍历每个字母的下标数组
for (int i = 0; i < 26; i++) {
vector<int> index = indice[i]; // 当前字母的下标数组
if (index.empty()) continue;
// 从小到大遍历当前字母所在下标
for (int j = 0; j < index.size(); j++) {
// 将当前字母添加进 answer 的条件:
// 下标大于 front 即上一个添加进 answer 的字母的下标 &&
// 当前下标后面的不同类字母种类 == 这一次添加需要其后面不同类字母的数量
if (index[j] > front && N[index[j]] == number) {
front = index[j];
answer.push_back(i + 'a');
flag1 = true;
flag2 = true;
indice[i].clear(); // 每添加一个字母就清空该字母对应的 index
// 维护数组 N
for (int temp = front; temp <= index.back(); temp++) N[temp]—;
break;
}
}
// 若该次循环有进行操作则进入下一次递归
if (flag2) break;
}
// 递归结束条件: 全部循环结束没有进行任何操作
if (!flag1) return answer;
return answer = search(indice, answer, N, number – 1, front);
}
string smallestSubsequence(string s) {
vector<vector<int>> indice(26); // indice 中记录每个字母出现的下标
int N[1001] = {0}; // N[i]=n 意为 s 中 i 位置后包含 n 种字母（不含 i 位置本身的字母）
set<char> temp;
for (int i = s.size() – 1; i >= 0; i—) {
if (!indice[s[i] – 'a'].empty()) N[i] = temp.size() – 1;
else N[i] = temp.size();
temp.insert(s[i]);
indice[s[i] – 'a'].emplace_back(i);
}
for (auto& index : indice) sort(index.begin(), index.end());
int number = temp.size() – 1;
string answer = "";
int front = –1;
answer = search(indice, answer, N, number, front);
return answer;
}
};
更优解法——单调栈
class Solution {
public:
string smallestSubsequence(string s) {
vector<int> last(26, –1), inStack(26, 0);
// 记录每个字母最后出现的位置
for (int i = 0; i < s.size(); i++) {
last[s[i] – 'a'] = i;
}
string stack;
for (int i = 0; i < s.size(); i++) {
char c = s[i];
int idx = c – 'a';
// 如果当前字符已经在栈中，跳过
if (inStack[idx]) continue;
// 当栈不为空，且栈顶字符大于当前字符，且栈顶字符在后面还会出现时，弹出栈顶
while (!stack.empty() && stack.back() > c && last[stack.back() – 'a'] > i) {
inStack[stack.back() – 'a'] = 0;
stack.pop_back();
}
// 当前字符入栈
stack.push_back(c);
inStack[idx] = 1;
}
return stack;
}
};
