单调栈--最小字典序

1081. Smallest Subsequence of Distinct Characters

Medium

15628FavoriteShare

Return the lexicographically smallest subsequence of ​​text​​​ that contains all the distinct characters of ​​text​​ exactly once.

Example 1:

Input: "cdadabcc" Output: "adbc"

Example 2:

Input: "abcd" Output: "abcd"

Example 3:

Input: "ecbacba" Output: "eacb"

Example 4:

Input: "leetcode" Output: "letcod"

Note:

1. ​​1 <= text.length <= 1000​​
2. ​​text​​ consists of lowercase English letters.

string smallestSubsequence(string text){
    stack<char> s;
    unordered_map<char,int> Map;
    unordered_set<char> Visited;
    string Result;
    for(int i = 0;i < text.length();i++){
        Map[text[i]] ++;
    }
    for(int i = 0;i < text.length();i ++){
        Map[text[i]] --;
        if(Visited.find(text[i]) != Visited.end()){
            continue;
        }
        while(!s.empty() && text[i] < s.top() && Map[s.top()] > 0){//--case : 1    要保证字符串中所有字符都包含在结果里，必须加入条件Map[s.top()]>0
                                                                   //--case : 2    如果不用保证最后的结果必须包含所有字符，就把这个条件删掉
            Visited.erase(s.top());
            s.pop();
        }
        s.push(text[i]);
        Visited.insert(text[i]);
    }
    while(!s.empty()){
        Result += s.top();
        s.pop();
    }
    reverse(Result.begin(),Result.end());
    return Result;
}