[数据结构与算法]【leetcode】316. 去除重复字母。 「单调栈」「哈希表」

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

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1：

输入：s = “bcabc”
输出：“abc”
示例 2：

输入：s = “cbacdcbc”
输出：“acdb”

提示：

1 <= s.length <= 104
s 由小写英文字母组成

思路:

首先来解读一下题目是什么意思.就是尽量按照字典序来排列顺序,但是不能出现重复的字母并且每个出现过的字母都要保留下来至少一个.也就是说符合字典序的就直接保留下来,如果不符合字典序的但是后续不会再出现的也要保留下来,但是如果后续还会出现的字母不符合字典序的话就直接剔除.还有一个就是如果遇到重复的字母时就直接跳过他,因为已经不需要他了hhh

我们可以使用单调栈来做这道题,如果遇到不符合字典序的字母时首先进行判断是否后续还会出现,如果后续不会再出现了就压入栈,要不然就弹出.

因此我们需要两个哈希表来进行字母映射,一个是存储字母出现次数的,一个是用来标记字母是否出现过的.

代码区:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int n = s.size();
        unordered_map<char, int> vis;//是否出现过的标记
        unordered_map<char, int> nums;//剩余出现次数
        string res;
        stack<char> stk;
        for(int i = 0; i < n; i++){
            nums[s[i]] ++;//先统计每个字母要出现的次数
        }
        for(int i = 0; i < n; i++){
            nums[s[i]]--;//出现了就使剩余出现次数减一
            if(vis[s[i]]){//如果这个字母已经在栈中了就跳过该字母
                continue;
            }
            while(!stk.empty() && s[i] < stk.top()){//如果栈非空并且新的字母比栈顶字母小就说明不符合字典序
                if(nums[stk.top()] == 0){//如果栈顶字母剩余出现的次数已经没了,这个已经是绝唱了,那么就不弹出了
                    break;
                }
                vis[stk.top()] = 0;//如果剩余次数还有的话就使该字母弹出,并且标记变为0
                stk.pop(); 
            }
            stk.push(s[i]);//如果是符合字典序的话就压入栈
            vis[s[i]] = 1;//同时标记上,该字母已经存在了
        }
        while(!stk.empty()){//将栈中的字母取出并且倒置
            res.insert(res.begin(), stk.top());
            stk.pop();
        }
        return res;
    }
};

新手上路,有错请指正;