Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LeetCode 316. 去除重复字母 #9

Open
yinxin630 opened this issue May 13, 2019 · 0 comments
Open

LeetCode 316. 去除重复字母 #9

yinxin630 opened this issue May 13, 2019 · 0 comments
Labels

Comments

@yinxin630
Copy link
Owner

yinxin630 commented May 13, 2019

题目

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('');
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant