1081. Smallest Subsequence of Distinct Characters

找出只含字母的字符串中的字典序最小的不含重复字符的字符序列

本题的一个关键点是字典序最小，另一个是序列，因此是顺序遍历然后为了字典序最小，我们需要贪心进行遍历，如果当前构造的子序列的最后字符还可以更小并且它在后面有出现，我们会优先采用更小的字符，然后用一个定长数组来保证不重复

时间复杂度：O(N) 空间复杂度：O(1)

string smallestSubsequence(string text) {
    int count[26] = {};
    int used[26] = {};
	// 扫描一遍进行字符计数
    for(auto c : text) ++count[c-'a'];
    string res = "";
    for(auto c : text) {
		// 去重
        if (used[c-'a']) {
            --count[c-'a'];
            continue;
        }

		// 字符串为空，直接选择
        while(!res.empty() && c < res.back() && count[res.back()-'a']>0) {
			// 去掉字典序大的字符
            used[res.back()-'a']=false;
            res.pop_back();
        }

		// 使用当前字典序最小的字符
        used[c-'a'] = true;
        --count[c-'a'];
        res.push_back(c);
    }
    return res;
}

#string #greedy

1080. Insufficient Nodes in Root to Leaf Paths 109. Convert Sorted List to Binary Search Tree