[数据结构与算法]leetcode1081. 不同字符的最小子序列

1081. 不同字符的最小子序列

返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

示例 1：

输入：s = “bcabc”
输出：“abc”

示例 2：

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

• 1 <= s.length <= 1000

• s 由小写英文字母组成

本题与316. 去除重复字母是一样的题目。如果没有接触过单调栈很难掌握本道题，看过一遍题解代码后，再做一次还是不会。如果只是知道最简单的单调栈，那么自己写这道题也会比较难下手。(正是本菜鸡的两次遇到这道题都卡住的体验)

题目的目的是返回 1. 包含所有不同的字符 2. 字典序最小 的子序列

与简单的比较字符大小的单调栈问题不同，本题还必须考虑到目标子序列包含所有不同的字符。

我们需要自行定义合适的优先关系，

优先关系：
后面未出现的字符>字典序小的字符>字典序大的字符

算法流程如下，以 s = "cbacdcbc"为例：

step 1 . 统计所有字符最后出现的位置

mp[a]=2
mp[b]=6
mp[c]=7
mp[d]=4

step 2. 单调栈运行

初始化栈，V=[]
遍历字符串s
0 c: 栈空，入栈，V=[c]
1 b: b<c且mp[c]>1, 栈弹出c, b入栈, V=[b]
2 a: a<b且mp[b]>2, 栈弹出b, a入栈, V=[a]
3 c: c>a, c入栈, V=[a, c]
4 d: d>c, d入栈, V=[a, c, d]
5 c: c<d, 但是mp[d]<5(意味着如果弹出d，后面字符串没有d), 且c已经在栈内使用过了，栈保持不变,V=[a, c, d]
6 b: b<d但是mp[d]<5, b入栈, V=[a, c, d, d]
7 c: c已经在栈内使用过了，栈保持不变

代码如下:

class Solution {
public:
    string smallestSubsequence(string s) {
        map<char, int> mp,used;
        int len = s.size();
        for(int i=0;i<len;i++)
            mp[s[i]]=i;

        vector<char> V;
        for(int i=0;i<len;i++){
            while(!used[s[i]]&&!V.empty()&&V.back()>s[i]&&mp[V.back()]>i){
                used[V.back()]=0;V.pop_back();
            }
            if(!used[s[i]]){V.push_back(s[i]);used[s[i]]=1;}
        }
        string ans;
        ans.resize(V.size());
        for(int i=0;i<V.size();i++)
            ans[i]=V[i];
        return ans;
    }
};

题解中有利用string api，效率更高的代码：

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string ans="";
        for(int i=0;i<s.size();i++){
            if(ans.find(s[i])==string::npos){
                while(ans.size()>0){
                    if(s[i]<=ans[ans.size()-1]&&s.find(ans[ans.size()-1],i)!=string::npos)
                        ans.erase(ans.size()-1);
                    else     break;
                }
                ans+=s[i];
            }
        }
        return ans;
    }
};