leetcode316 去除重复字母

思路：

贪心 + 单调栈。

实现：

 1 class Solution
 2 {
 3 public:
 4     string removeDuplicateLetters(string s)
 5     {
 6         int n = s.length();
 7         stack<char> st;
 8         vector<int> cnt(26, 0);
 9         for (int i = 0; i < n; i++)
10         {
11             cnt[s[i] - 'a']++;
12         }
13         vector<bool> vis(26, false);
14         for (int i = 0; i < n; i++)
15         {
16             if (vis[s[i] - 'a']) { cnt[s[i] - 'a']--; continue; }
17             while (!st.empty() and s[i] <= st.top() and cnt[st.top() - 'a'] > 1)
18             {
19                 cnt[st.top() - 'a']--;
20                 vis[st.top() - 'a'] = false;
21                 st.pop();
22             }
23             st.push(s[i]);
24             vis[s[i] - 'a'] = true;
25         }
26         string res = "";
27         while (!st.empty()) { res += st.top(); st.pop(); }
28         reverse(res.begin(), res.end());
29         return res;
30     }
31 };