Leetcode-316-去除重复的字母

Leetcode-316-去除重复字母

题目描述

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

示例 1:

输入: "bcabc"
输出: "abc"


示例 2:

输入: "cbacdcbc"
输出: "acdb"

方法：栈+哨兵

思路分析：

• 首先解释一下什么是字典序。
  • 字典序是指从前到后比较两个字符串的大小
  • 首先比较第一个字符，如果不同则第一个字符较小的字符串更小
  • 如果相同则继续比较第二个字符…. 如果比到最后都一样的话，那么两个字符串相等

观察示例 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

• 下面我们就要思考，当遍历到字符串ASCII 值减少的时候，应该如何处理。（一种最理想的情况是：abcd，在遍历的时候，遇到的字符串的 ASCII 值逐渐增大。）

还看示例 1：
已经读到了 bc，已经是字典序最小的排列。
即将读到的 a 比 c 的 ASCII 值小。如果 a 能排在 c 之前，就能得到一个比 ca 更小的字典序 ac。
那么 a 能不能排在 c 之前，就看 a 的后面还会不会出现字符 c，显然会。同理，由于字符 b 在将来还会出现，构成的字典序更小，因此舍弃之前的字符 b。
到此为止，应该想到我们需要借助栈帮助我们完成这题。

• 然后根据这个思路，我们再看一下示例 2：cbacdcbc。

第 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 比之前的 d 小，但是，后面不会再出现 d 了，因此 b 就应该放在这个位置，因此让 b 入栈，此时栈中元素 [a, c, d, b]；

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

• 于是：我们可以设计如下算法：

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

• 因为需要判断读到的字符在栈中是否已经存在，因此可以使用哈希表，又因为题目说，字符只会出现小写字母，用一个布尔数组也是可以的，注意在出栈入栈的时候，需要同步更新一下这个布尔数组。

• 又因为要判断栈顶元素在后面是否会被遍历到，因此我们需要首先遍历一次字符，存一下这个字符最后出现的位置，就能判断栈顶元素在后面是否会被遍历到

1. 未使用哨兵的版本

class Solution {
    public String removeDuplicateLetters(String s) {
        int len = s.length();
        // 1. 特判
        if(len < 2){                            // 这里说明长度为0或者1，直接添加即可
            return s;
        }

        // 2. 记录每个字符串已经出现的字符,并且记录每个字符出现的最后一个位置
        boolean[] set = new boolean[26];
        int[] lastIndex = new int[26];
        for(int i = 0;i < len;++i){
            lastIndex[s.charAt(i) - 'a'] = i;   // 记录每个字符串出现的最后index
        }


        // 3. 用栈做判断
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < len;++i){
            char curr = s.charAt(i);
            if(set[curr - 'a']){                // 如果这个字符栈里面已经存在
                continue;
            }

            // 3.1 对入栈元素进行判断
            // lastIndex[stack.peek() - 'a'] >= i 说明该字符后面还会再次出现
            // stack.peek() > curr 说明栈顶字符比当前入栈元素的字典序大
            while(!stack.isEmpty() && stack.peek() > curr && lastIndex[stack.peek() - 'a'] > i){
                char top = stack.pop();
                set[top - 'a'] = false;
            }

            // 3.2 不满足上述while 循环条件: 直接加入到栈中就好
            stack.push(curr);
            set[curr - 'a'] = true;
        }

        // 4. 栈顶元素一次出现并且返回字符串形式
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.insert(0,stack.pop());
        }
        return sb.toString();
    }
}

使用哨兵原因：里面判断语句太长，每一次都要判断栈是否为空。这里使用一个哨兵的技巧，一开始就在栈里面放一个最小字符’a’ 。因为后面判断语句stack.peek() > currentChar 这里是严格符号，因此这个 a 一定不会被弹出。

while (!stack.empty() && stack.peek() > currentChar && lastAppearIndex[stack.peek() - 'a'] >= i) {
    char top = stack.pop();
    set[top - 'a'] = false;
}

使用哨兵：

class Solution {
    public String removeDuplicateLetters(String s) {
        int len = s.length();
        // 1. 特判
        if(len < 2){
            return s;
        }

        // 2.1 记录每个字符出现的最后一个位置，并且记录当前的字符是否已经出现过
        int[] lastIndex = new int[26];
        boolean[] set  = new boolean[26];                   // 用于记录当前的字符是否已经出现过
        char[] chars = s.toCharArray();
        for(int i = 0;i < len;i++){
            lastIndex[chars[i] - 'a'] = i;                  // 记录每个字符出现的最后一个位置
        }

        // 2.2 使用哨兵 ： 栈初始化的时候就加入哨兵 : 字符'a'
        LinkedList<Character> stack = new LinkedList<>();
        stack.addLast('a');

        // 3. 栈做判断
        for(int i = 0;i < len;i++){
            char curr = chars[i];
            if(set[curr - 'a']){                            // 说明当前字符之前已经出现过
                continue;
            }

            // 3.1 栈顶元素比当前元素大 且 这个字符后面还会再次出现
            while(stack.getLast() > curr && lastIndex[stack.getLast() - 'a'] > i){
                char top = stack.removeLast();              // 弹出栈顶元素
                set[top - 'a'] = false;                     // 将字符改为出现过
            }
            // 3.2 不满足while循环条件 ： 说明当前字符字典序是升序的 或者 当前字符之前没有出现过
            stack.addLast(curr);
            set[curr - 'a'] = true;
        }

        // 4. 转为字符串返回结果
        StringBuilder sb = new StringBuilder();
        stack.removeFirst();
        while(!stack.isEmpty()){
            sb.append(stack.removeFirst());
        }
        return sb.toString();
    }
}

复杂度分析：

• 时间复杂度：O(N)，这里 N 是字符的长度；
• 空间复杂度：O(N) ，最坏情况下，这个字符串本身就是字典序最小的字符串，栈中就要存字符串长度这么多的字符串。

关于栈的题目

「力扣」第 20 题：有效的括号（简单）
「力扣」第 71 题：简化路径（中等）
「力扣」第 150 题：逆波兰表达式求值（中等）
「力扣」第 32 题：最长有效括号（困难）
「力扣」第 739 题：每日温度（中等）
「力扣」第 496 题：下一个更大元素 I（简单）
「力扣」第 84 题：柱状图中最大的矩形（困难）
「力扣」第 42 题：接雨水（困难）
「力扣」第 901 题：股票价格跨度（中等）
「力扣」第 581 题：最短无序连续子数组（中等）
「力扣」第 402 题：移掉K位数字（中等）
「力扣」第 321 题：拼接最大数（困难）
「力扣」第 1673 题：找出最具竞争力的子序列（中等）

打赏