贪心思路及证明
时间复杂度:O(n)
代码实现
class Solution {
public:
string removeDuplicateLetters(string s)
{
string ans;
unordered_map<char, bool> ins; // 记录这个字母是否在, ans 里面出现过
unordered_map<char, int> last; // 记录原字符串每一个字母出现的最右边的位置
for(int i = 0; i < s.size(); i++) last[s[i]] = i;
for(int i = 0; i < s.size(); i++)
{
if(ins[s[i]] == true) continue; // 这个字母在 ans 里面出现过了,就不用再加入了
while(ans.size() && ans.back() > s[i] && last[ans.back()] > i) // 不是 last[s[i]] > i
{ // ans 不为空 最后一个字母字典序大于当前字母 ans 最后一个字母在后面有出现过
// ins[s[i]] = false;
ins[ans.back()] = false;
ans.pop_back();
}
ans += s[i];
ins[s[i]] = true;
}
return ans;
}
};