LeetCode 316. 去除重复字母

[yinxin630]

题目

https://leetcode-cn.com/problems/remove-duplicate-letters/

思路

1. 贪心算法, 用栈存储 result
2. 记录各字母出现次数, 备用
3. 对于每个字母
   a. 如果 result 中已经有了, 则直接弃掉
   b. 如果当前字母小于栈顶字母, 并且栈顶字母计数大于0(即后面还有), 则抛弃当前栈顶元素
   c. 然后将当前字母入栈
4. 初始值设为 ['0'] 是为了方便初始处理, 因为所有字母都大于 '0'

代码

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    if (s.length === 0) {
        return '';
    }

    const count = {};
    for (let i = 0; i < s.length; i++) {
        count[s[i]] = (count[s[i]] || 0) + 1;
    }

    const result = ['0'];
    for (let i = 0; i < s.length; i++) {
        count[s[i]]--;

        if (result.indexOf(s[i]) !== -1) {
            continue;
        }

        while (true) {
            const top = result[result.length - 1];
            if (count[top] > 0 && s[i] < top) {
                result.pop();
            } else {
                break;
            }
        }
        result.push(s[i]);
    }

    return result.slice(1).join('');
};