题目描述
返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
示例 1：
输入："cdadabcc"
输出："adbc"
题目解析
- 详细描述一下题目，要求是字符串中所有字母均要出现，且只出现一次，且返回字典序最小的子序列。
- 构建栈维护最终结构，构建贪心策略，当栈顶元素比处理字符大时，且后续字母还包含栈顶元素时，进行栈中淘汰，同时记录处理字符状态，若栈中已包含了该字符，则不处理该字符。
C++代码
class Solution {
public:
string smallestSubsequence(string text) {
stack<int> ansStack;
int nums[26];
memset(nums, 0, sizeof(nums));
for(int i = 0;i < text.size(); i++) {
nums[text[i] - 'a']++;
}
int status = 0;
for(int i = 0; i < text.size(); i++) {
if((status & (1 << (text[i] - 'a'))) == 0) {
while(ansStack.size() > 0 && ansStack.top() >= text[i] - 'a' && nums[ansStack.top()] > 0) {
status ^= (1 << ansStack.top());
ansStack.pop();
}
ansStack.push(text[i] - 'a');
status |= (1 << ansStack.top());
}
nums[text[i] - 'a']--;
}
string ans(ansStack.size(), 'a');
int idx = ansStack.size();
while(ansStack.size()) {
ans[--idx] = ansStack.top() + 'a';
ansStack.pop();
}
return ans;
}
};
