贪心方法
用一个两个数组vector<int>cnt,vector<bool>in_right_place；
string res:目前符合条件的字符串，到代码结束的时候，这个res才是正确的答案
cnt数组 用于记录每个char未来会出现的次数，in_right_place数组判断这个char是否已经在正确的位置上
什么叫做未来会出现呢？
我们拿样例做为例子：
输入: "bcabc"
我们先遍历一遍所有字符串记录cnt
结果是cnt['a']=1,cnt['b']=2,cnt['c']=2,其他都为0
我们需要再遍历一遍寻找结果
现在读到第一个字符b,未来会出现的'b'的次数就减去1（因为已经出现了一次了），所以未来b只会再出现(2-1)次，这就是未来出现的次数
in_right_place判断正确位置比较好理解，我们每次读到一个未在正确位置上的字符，就可以将这个字符拿来和res比较字典序，
如果能发现存在一个新字符串使得字典序更小，则代替。
如何判断字典序更小呢？
通过这个:
while(cnt[res.back()]>0&&读取的当前字符<res.back()){
/*就能说明存在一个新序列使得字典序更小*/
in_right_place[res.back()]=false;
res.pop_back();
/*撤销正确位置的标记并将其从结果字符串弹出*/
}
还是回到样例，假设当前读取的字符为s[2]，即'a'，此时的res="bc"
=>‘a’比'c'字典序优先且'c'未来还会出现(即cnt['c']>0),说明存在'a'在'c'前面的搭配，所以弹出'c'并撤销'c'是正确位置的标记即in_right_place['c']=false;此时res="b"
=>‘a’比'b'字典序优先且'b'未来还会出现(即cnt['b']>0),说明存在'a'在'b'前面的搭配，所以弹出'b'并撤销'b'是正确位置的标记即in_right_place['b']=false;此时res=""
这一题的贪心在于，每次遍历会考虑后面的情况将res改变。具体实现代码如下:
C++实现代码如下：
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int>cnt();
vector<bool>in_right_place();
for(char c:s){
cnt[c]++;
}
string res="";
/*返回的字符串初始化为空*/
for(char c:s){
cnt[c]--;
if(in_right_place[c]){
/*如果已经在正确位置，则跳过*/
continue;
}else{
while(cnt[res.back()]>&&c<res.back()){
/*说明存在一个新序列使得字典序更小*/
in_right_place[res.back()]=false;
res.pop_back();
/*撤销正确位置的标记并将其从结果字符串弹出*/
}
res+=c;
in_right_place[c]=true;
/*此时c在“当前的”正确位置*/
}
}
return res;
}
};
也可以不用vector而用数组记录
class Solution {
public:
string removeDuplicateLetters(string s) {
int m[] = {}, visited[] = {};
string res = "";
for (auto a : s) m[a]++;
for (auto a : s) {
--m[a];
if (visited[a]) continue;
while (a < res.back() && m[res.back()]) {
visited[res.back()] = ;
res.pop_back();
}
res += a;
visited[a] = ;
}
return res;
}
};