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

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

注意：该题与 316 https://leetcode.com/problems/remove-duplicate-letters/ 相同

示例 1：

输入：s = “bcabc”
输出：”abc”
示例 2：

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

/**
 * @param {string} s
 * @return {string}
 */
var smallestSubsequence = function (s) {
    // 存放去重的结果
    let stack = [];
    // 维护一个计数器记录字符串中字符的数量
    // 因为输入为 ASCII 字符，大小 256 够用了
    let count = new Array(256).fill(0);
    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i)]++;
    }
    let inStack = [];
    for (let c of s) {
        // 每遍历过一个字符，都将对应的计数减一
        count[c.charCodeAt(0)]--;
        // 如果字符 c 存在栈中，直接跳过
        if (inStack[c]) continue;
        // 插入之前，和之前的元素比较一下大小
        // 如果字典序比前面的小，pop 前面的元素
        while (
            stack.length &&
            stack[stack.length - 1].charCodeAt(0) > c.charCodeAt(0)
        ) {
            // 若之后不存在栈顶元素了，则停止 pop
            if (count[stack[stack.length - 1].charCodeAt(0)] == 0) {
                break;
            }
            // 若之后还有，则可以 pop
            // 弹出栈顶元素，并把该元素标记为不在栈中
            inStack[stack.pop()] = false;
        }
        // 若不存在，则插入栈顶并标记为存在
        stack.push(c);
        inStack[c] = true;
    }
    return stack.join("");
};