LeetCode316 去除重复字母

发表于 | 分类于 |
字数统计: 279 | 阅读时长 ≈ 1

链接: 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;
    }
};