一、题目
二、思路
先读懂题意，删除重复的字母，得到最小的字符串。如babc，删除重复字母有两种结果bac,abc。abc小于bac，所以答案是abc。
遇到一个新字符 如果比栈顶小 并且在新字符后面还有和栈顶一样的 就把栈顶的字符抛弃了。
（1）前者的条件即单调栈的步骤（for中带while）；可以用哈希表inst统计当前字符是否在栈中。
（2）为了满足后者的条件，即如果栈顶元素大于当前遍历到的字符s[i]，并且栈顶元素在后面还存在，所以可以放心的pop掉。可以用哈希表cnt统计s中剩余字符的出现次数。
（3）上面的循环操作后，得到最后的栈，把栈底到栈顶元素串成字符串。
三、代码
class Solution { public: string removeDuplicateLetters(string s) { stack<char> st; //剩余字符出现次数的哈希表 unordered_map<char, int> cnt; //当前字符是否存在栈中 unordered_map<char, bool> inst; for(auto& c: s){ ++cnt[c]; } for(int i= 0; i < s.size(); i++){ char c = s[i]; //当前字符已经在栈中则跳出循环 if(inst[c]){ --cnt[c]; continue; } //栈顶元素大于当前字符，并且栈顶元素在后面还存在,所以可以pop while(!st.empty() && st.top() > c && cnt[st.top()] > 0){ inst[st.top()] = false; st.pop(); } st.push(c); --cnt[c]; //当前c字符存在栈中 inst[c] = true; } string res; //把栈底到栈顶元素串成字符串 while(!st.empty()){ res = st.top() + res; st.pop(); } return res; } };
