【C++】316 去除重复字母

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

#include 
#include 
#include 

using namespace std;

string removeDuplicateLetters(string s) {
    stack<char> st; // 使用栈来存储最终的结果字符
    unordered_map<char, int> last_occurrence; // 记录每个字符最后出现的位置
    unordered_map<char, bool> visited; // 记录每个字符是否已经在栈中

    // 记录每个字符最后出现的位置
    for (int i = 0; i < s.length(); ++i) {
        last_occurrence[s[i]] = i;
    }

    // 遍历字符串
    for (int i = 0; i < s.length(); ++i) {
        // 如果当前字符已经在栈中，则跳过
        if (visited[s[i]]) {
            continue;
        }

        // 如果栈顶字符比当前字符大，并且栈顶字符在后面还会出现，则弹出栈顶字符
        while (!st.empty() && st.top() > s[i] && last_occurrence[st.top()] > i) {
            visited[st.top()] = false;
            st.pop();
        }

        // 将当前字符入栈，并标记为已访问
        st.push(s[i]);
        visited[s[i]] = true;
    }

    // 构造最终的结果字符串
    string result;
    while (!st.empty()) {
        result = st.top() + result;
        st.pop();
    }

    return result;
}

int main() {
    string s = "bcabc";
    string result = removeDuplicateLetters(s);
    cout << "Result: " << result << endl; // 输出结果为 "abc"
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

时间复杂度分析：

遍历字符串以构建 last_occurrence 字典：O(n)，其中 n 是字符串的长度。
遍历字符串以构建最终的结果字符串：O(n)，其中 n 是字符串的长度。 总的时间复杂度为 O(n)。
空间复杂度分析：

使用了一个栈 st 来存储结果字符串中的字符，最坏情况下栈的大小会达到字符串的长度，因此空间复杂度为 O(n)。
使用了两个辅助的哈希表 last_occurrence 和 visited，它们最多存储字符串中出现的不同字符，因此空间复杂度也为 O(n)。 总的空间复杂度为 O(n)。