去除重复字母

题目链接:https://leetcode-cn.com/problems/remove-duplicate-letters/
题目描述:
去除重复字母

题解:
1.遍历字符串,记录字符出现次数。
2.定义标记数组,记录字符是否重复出现过。
3.为了确保返回结果的字典序最小,使用单调栈。


class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> map;
        vector<int> visit(26, 0);   //标记数组
        for(char ch: s)
        {
            map[ch]++;
        }

        string result;   //定义单调栈
        for(char ch: s)
        {
            if(visit[ch - ‘a‘] == 0)    //字符未出现过
            {
                while(!result.empty() && result.back() > ch)    //若新字符小于栈顶字符,且栈顶字符之后存在重复,则替换当前值为新字符,否则不变化
                {
                    if(map[result.back()] > 0)
                    {
                        visit[result.back() - ‘a‘] = 0;
                        result.pop_back();
                    }else
                    {
                        break;
                    }
                       
                }
                result.push_back(ch);
                visit[ch - ‘a‘] = 1;
            }
            map[ch] -= 1;
        }
        return result;
    }
};

去除重复字母

上一篇:JS学习笔记02-初识原型


下一篇:JS OffsetParent属性