美文网首页算法代码
去除重复字母(栈和哨兵)

去除重复字母(栈和哨兵)

作者: windUtterance | 来源:发表于2020-05-17 11:50 被阅读0次

    题目描述
    给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

    示例
    输入: "cbacdcbc"
    输出: "acdb"
    首先解释一下字典序。字典序是指从前到后比较两个字符串大小的方法

    首先比较第 1 个字符,如果不同则第 1 个字符较小的字符串更小;
    如果相同则继续比较第 2 个字符 …… 如此继续,比较整个字符串的大小。
    观察示例 1:bcabc。

    字符 a 在字符串中只出现一次,根据题目要求,字符 a 必须被选取;
    字符 b 出现了两次,显然选择 a后面的那个,因为字典序 ab 在 ba 前面。同理,有两个相同的字符 c ,我们选择后一个。因此,输出就是 abc。
    再观察示例 2:cbacdcbc。

    有 4 个字符:a、b、c、d。其中 a 和 d 只出现一次,必须被选取;
    b 出现 2 次,一个在 a 前面,一个在 a 后面,显然保留在 a 后面的;
    c 出现 4 次,我们把几种可能都列出来观察一下:
    情况 1:cadb
    情况 2:acdb(字典序最小)
    情况 3:adcb
    情况 4:adbc

    一种最理想的情况是:abcd,在遍历的时候,遇到的字符串的 ASCII 值逐渐增大。

    下面我们就思考,当遍历到的字符的 ASCII 值减少的时候,应该如何处理。

    还看示例 1:已经读到了 bc,已经是字典序最小的排列。

    即将读到的 a 比 c 的 ASCII 值小。如果 a 能排在 c 之前,就能得到一个比 ca 更小的字典序 ac。

    那么 a 能不能排在 c 之前,就看 a 的后面还会不会出现字符 c,显然会。同理,由于字符 b 在将来还会出现,构成的字典序更小,因此舍弃之前的字符 b。

    到此为止,应该想到我们需要借助栈帮助我们完成这题。

    然后根据这个思路,我们再看一下示例 2:cbacdcbc。

    栈.png

    第 1 步:读到 c,入栈,此时栈中元素 [c];

    第 2 步:读到 b,b 比之前 a 小,c 在以后还会出现,因此 c 出栈,b 入栈,此时栈中元素 [b];

    第 3 步:读到 a,a 比之前 b 小,b 在以后还会出现,因此 b 出栈,a 入栈,此时栈中元素 [a];

    第 4 步:读到 c,c 比之前 a 大,直接让 c 入栈,此时栈中元素 [a, c];

    第 5 步:读到 d,d 比之前 d 大,直接让 d 入栈,此时栈中元素 [a, c, d];

    第 6 步:读到 c,这里要注意:此时栈中已经有 c 了,此时栈中元素构成的字符顺序就是最小的字典序,不可能舍弃之前的 c,而用现在的读到的 c,因此这个 c 不需要,直接跳过;

    第 7 步:读到 b,b 比之前的 c 小,但是,后面不会再出现 b 了,因此 b 就应该放在这个位置,因此让 b 入栈,此时栈中元素 [a, c, d, b];

    第 8 步:读到 c,同第 6 步,这个 c 我们不需要。

    于是,我们可以设计如下算法:

    1、遍历字符串里的字符,如果读到的字符的 ASCII 值是升序,依次存到一个栈中;
    2、如果读到的字符在栈中已经存在,这个字符我们不需要;
    3、如果读到的 ASCII 值比栈顶元素严格小,看看栈顶元素在后面是否还会出现,如果还会出现,则舍弃栈顶元素,而选择后出现的那个字符,这样得到的字典序更小。

    因为需要判断读到的字符在栈中是否已经存在,因此可以使用哈希表,又因为题目中说,字符只会出现小写字母,用一个布尔数组也是可以的,注意在出栈入栈的时候,需要同步更新一下这个布尔数组。
    又因为要判断栈顶元素在后面是否会被遍历到,因此我们需要先遍历一次字符,存一下这个字符最后出现的位置,就能判断栈顶元素在后面是否会被遍历到。

    作者:liweiwei1419
    链接:https://leetcode-cn.com/problems/remove-duplicate-letters/solution/zhan-by-liweiwei1419/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    Java代码

    class Solution {
        public String removeDuplicateLetters(String s) {
            int len = s.length();
            if (len < 2) return s;
    
            // 记录是否在已经得到的字符串中
            boolean[] set = new boolean[26];
            // 记录每个字符出现的最后一个位置
            int[] lastAppearIndex = new int[26];
            for(int i = 0;i < len;i++) {
                lastAppearIndex[s.charAt(i) - 'a'] = i;
            }        
    
            Deque<Character> stack = new ArrayDeque<>();
            // 此时 `a` 作为哨兵,这个 `a` 永远不会被弹出
            // 如此一来,在遍历的时候,就不用判断栈是否为空了
            stack.push('a');
    
            for(int i = 0;i < len;i++) {
                char curChar = s.charAt(i);
                if(set[curChar - 'a']) continue;
    
                while(stack.peek() > curChar && lastAppearIndex[stack.peek() - 'a'] >= i) {
                    char top = stack.pop();
                    set[top - 'a'] = false;
                }
    
                stack.push(curChar);
                set[curChar - 'a'] = true;
            }
            
            int size = stack.size();
            StringBuilder result = new StringBuilder();
            for(int i = 0;i < size - 1;i++) {
                result.insert(0, stack.pop());  //这里用append会出错,暂时懒得查append和insert的区别了
            }
    
            return result.toString();
        }
    }
    

    相关文章

      网友评论

        本文标题:去除重复字母(栈和哨兵)

        本文链接:https://www.haomeiwen.com/subject/gxpjohtx.html