题目链接:https://leetcode-cn.com/problems/remove-duplicate-letters/
题目描述:
题解:
1.遍历字符串,记录字符出现次数。
2.定义标记数组,记录字符是否重复出现过。
3.为了确保返回结果的字典序最小,使用单调栈。
class Solution {
public:
string removeDuplicateLetters(string s) {
unordered_map<char, int> map;
vector<int> visit(26, 0); //标记数组
for(char ch: s)
{
map[ch]++;
}
string result; //定义单调栈
for(char ch: s)
{
if(visit[ch - ‘a‘] == 0) //字符未出现过
{
while(!result.empty() && result.back() > ch) //若新字符小于栈顶字符,且栈顶字符之后存在重复,则替换当前值为新字符,否则不变化
{
if(map[result.back()] > 0)
{
visit[result.back() - ‘a‘] = 0;
result.pop_back();
}else
{
break;
}
}
result.push_back(ch);
visit[ch - ‘a‘] = 1;
}
map[ch] -= 1;
}
return result;
}
};