「力扣」第 316 题：去除重复字母（困难）

栈
专题 7：栈
发布日期:   2017-09-15

「力扣」第 316 题：去除重复字母（困难）

我写的题解地址：

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-letters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

同「力扣」第 1081 题：1081. 不同字符的最小子序列。

方法：使用栈

1、栈里永远存放的是目前看到的字典序最小的子序列；

2、什么时候栈顶出栈？（1）非空；（2）字典序：栈顶 > 新来的字符；（3）栈顶元素在以后还会看到。

此时，可以得到一个字典序更小的子序列。

3、如果新来的字符，栈里没有，并且以后也不会看到，就必须添加；

如果新来的字符，栈里有，就不用管了，因为如果抛弃了栈里的，得到的字典序更大。

![image-20191207212106043](/Users/liwei/Library/Application Support/typora-user-images/image-20191207212106043.png)

Java 代码：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class Solution {

    public String removeDuplicateLetters(String s) {
        int len = s.length();
        // 预处理，我把一个字符出现的最后一个位置记录下来
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(s.charAt(i), i);
        }

        // 保存已经出现过的
        Set<Character> set = new HashSet<>();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < len; i++) {

            Character curChar = s.charAt(i);
            if (set.contains(curChar)) {
                continue;
            }

            // 注意：这里条件判断语句很长，map.get(stack.peek()) 不要写成了 map.get(curChar)
            while (!stack.isEmpty() && map.get(stack.peek()) > i && curChar < stack.peek()) {
                // 出栈的同时，也要从哈希表中移除
                set.remove(stack.pop());
            }

            stack.push(curChar);
            set.add(curChar);
        }

        StringBuilder stringBuilder = new StringBuilder();
        while (!stack.isEmpty()) {
            stringBuilder.insert(0, stack.pop());
        }

        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String res = solution.removeDuplicateLetters("cbacdcbc");
        System.out.println(res);
    }
}

参考资料

1、https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/solution/mei-you-qi-ji-yin-qiao-zhi-you-chun-cui-de-tan-xin/

Java 代码：

import java.util.Stack;

public class Solution {

    // 贪心算法

    public String removeDuplicateLetters(String s) {
        // 计算 26 字母数量
        int[] charsCount = new int[26];
        // 标记字母是否已经入栈
        boolean[] visited = new boolean[26];
        int len = s.length();
        char[] sChars = s.toCharArray();
        for (char c : sChars) {
            charsCount[c - 'a']++;
        }
        Stack<Character> stack = new Stack<>();
        // 最终字符的长度
        int index = 0;
        for (int count : charsCount) {
            if (count > 0) {
                index++;
            }
        }

        char[] res = new char[index];
        // len 是字符串的长度
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            // 有小字符的且满足其前面的字符在小字符后还有同样字符的，则出栈
            while (!stack.isEmpty() && c < stack.peek() && charsCount[stack.peek() - 'a'] > 1 && !visited[c - 'a']) {
                Character pop = stack.pop();
                visited[pop - 'a'] = false;
                charsCount[pop - 'a']--;
            }
            if (visited[c - 'a']) {
                //重复的字符根据游标往后移动，数量减一
                charsCount[c - 'a']--;
                continue;
            }
            stack.push(c);
            visited[c - 'a'] = true;
        }

        while (!stack.isEmpty()) {
            res[--index] = stack.pop();
        }
        return String.valueOf(res);
    }
}

Java 代码：

import java.util.Stack;

public class Solution {

    public String removeDuplicateLetters(String s) {
        int len = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (stack.contains(s.charAt(i))) {
                continue;
            }
            while (!stack.isEmpty() && s.charAt(i) < stack.peek() && s.indexOf(stack.peek(), i) != -1) {
                stack.pop();
            }
            stack.add(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        for (Character c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }
}

LeetCode 第 316 题：去除重复字母（困难）

传送门：LeetCode 第 316 题：去除重复字母。

同 LeetCode 第 1081 题：不同字符的最小子序列。

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-letters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析：

首先解释一下字典序是什么。

字典序

字典序是指从前到后比较两个字符串大小的方法。

  • 首先比较第 1 个字符，如果不同则第 1 个字符较小的字符串更小；
  • 如果相同则继续比较第 2 个字符 …… 如此继续，比较整个字符串的大小。

整理题目要求：

1、去除字符串中重复的字母，使得每个字母只出现一次；

2、保证返回结果的字典序最小；

3、不能打乱其他字符的相对位置。

观察示例 1：bcabc。

  • 如果某个字符在字符串中只出现一次，那么这个字符串必须被选取，这里 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 值小。这时候看字符 c 在后面还会不会出现，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 比之前的 c 小，但是，后面不会再出现 b 了，因此 b 就应该放在这个位置，因此让 b 入栈，此时栈中元素 [a, c, d, b]；

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

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

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

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

参考代码 1：

import java.util.Stack;

public class Solution {

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

        // 记录是否在已经得到的字符串中
        boolean[] set = new boolean[26];

        // 记录每个字符出现的最后一个位置
        int[] indexes = new int[26];
        for (int i = 0; i < len; i++) {
            indexes[s.charAt(i) - 'a'] = i;
        }

        Stack stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char currentChar = s.charAt(i);
            if (set[currentChar - 'a']) {
                continue;
            }

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

            stack.push(currentChar);
            set[currentChar - 'a'] = true;
        }

        StringBuilder stringBuilder = new StringBuilder();
        while (!stack.empty()) {
            stringBuilder.insert(0, stack.pop());
        }
        return stringBuilder.toString();
    }
}

Java 代码：

import java.util.Stack;

/**
 * @author liwei
 * @date 2019/6/27 10:26 AM
 */
public class Solution2 {

    public String removeDuplicateLetters(String s) {
        int len = s.length();
        Stack stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (stack.contains(s.charAt(i))) {
                continue;
            }
            while (!stack.isEmpty() && s.charAt(i) < stack.peek() && s.indexOf(stack.peek(), i) != -1) {
                stack.pop();
            }
            stack.add(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        for (Character c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }
}

Java 代码：

import java.util.Stack;

public class Solution {

    // 贪心算法

    public String removeDuplicateLetters(String s) {
        // 计算 26 字母数量
        int[] charsCount = new int[26];
        // 标记字母是否已经入栈
        boolean[] visited = new boolean[26];
        int len = s.length();
        char[] sChars = s.toCharArray();
        for (char c : sChars) {
            charsCount[c - 'a']++;
        }
        Stack<Character> stack = new Stack<>();
        // 最终字符的长度
        int index = 0;
        for (int count : charsCount) {
            if (count > 0) {
                index++;
            }
        }

        char[] res = new char[index];
        // len 是字符串的长度
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            // 有小字符的且满足其前面的字符在小字符后还有同样字符的，则出栈
            while (!stack.isEmpty() && c < stack.peek() && charsCount[stack.peek() - 'a'] > 1 && !visited[c - 'a']) {
                Character pop = stack.pop();
                visited[pop - 'a'] = false;
                charsCount[pop - 'a']--;
            }
            if (visited[c - 'a']) {
                //重复的字符根据游标往后移动，数量减一
                charsCount[c - 'a']--;
                continue;
            }
            stack.push(c);
            visited[c - 'a'] = true;
        }

        while (!stack.isEmpty()) {
            res[--index] = stack.pop();
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String res =solution.removeDuplicateLetters("bcabc");
        System.out.println(res);
    }
}

Python 代码：

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        size = len(s)
        stack = []

        for i in range(size):
            if stack.count(s[i]) > 0:
                continue
            while stack and ord(s[i]) < ord(stack[-1]) \
                    and s.find(stack[-1], i) != -1:
                stack.pop()



            stack.append(s[i])
        return ''.join(stack)
文章作者： liweiwei1419
文章链接： https://liweiwei1419.gitee.io/leetcode-algo/2017/09/15/leetcode-algo/0316-remove-duplicate-letters/
版权声明： 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
栈
赏
评论
  目录