LeetCode316 去除重复字母

链接: https://leetcode.cn/problems/remove-duplicate-letters/

题意

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

解法

卡了好久
想到了可能要用单调栈 但就是差一点
首先统计每个字符的出现次数
单调栈处理
如果当前字符已经出现在字符串里了,那就一定是最优的位置了
否则进行判断
如果栈顶字符比字符大且后续还有这个栈顶字符
就把当前栈顶字符pop掉
处理到字符串最后一个字符

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<char> stk;
unordered_map<char, int> cnt;
unordered_map<char, int> have;
for (char ch: s) cnt[ch]++;
string ret = "";
for (int i = 0; i < s.size(); i++) {
if (!have[s[i]]){
while (ret.size() && s[i] < ret.back() && cnt[ret.back()] > 0) {
have[ret.back()] = 0;
ret.pop_back();
}
ret += s[i];
have[s[i]] = 1;
}
cnt[s[i]]--;

}
return ret;
}
};