参考文献
ref{:target=”_blank”}
贪心算法
C++ 代码
class Solution {
public:
// 贪心策略,如果 1. res.back > now, 且 rec.back 可以删除,2. nowm没有添加过,就删除back;
// 可以删除含义:后面还有该字符
string removeDuplicateLetters(string s) {
unordered_map<char, int> last; // 每个字符最后一次出现位置
for(int i = 0; i<s.size(); ++i) {
char c = s[i];
last[c] = i;
}
unordered_map<char, bool> vis; // 字符是否之前出现过
string res;
for(int i=0; i<s.size(); ++i){
char c = s[i];
if(vis[c])continue;
while(res.size() && res.back() > c && last[res.back()]>i){
vis[res.back()] = false;
res.pop_back();
}
res.push_back(c);
vis[c] = true;
}
return res;
}
};