去除重复字母

发表于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode每日一题，316.Remove Duplicate Letters

先看题目描述

ral74A.png

大意就是给定一个字符串 s，让我们去除其中的重复字母，要求返回结果的字典序最小，且不打乱字母的相对顺序

算法和思路

贪心+单调栈

这题的思路和 402. 移除k位数字 有点像，但还是有些区别

对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，例如，对于 A = 1axxx，B = 1bxxx，如果 a > b 则 A > B

基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小

贪心策略如下：

  • 用一个数组 count 记录 s 中每个字母的出现次数，布尔数组 exist 来记录栈中是否已存在某个字母
  • 遍历 s 中字母 c，若栈中已存在字母 c，则跳过；否则，若栈顶元素大于 c 且其剩余出现次数大于 0，则删除栈顶元素直至栈为空或栈顶元素小于 c 或栈顶元素的剩余出现次数为 0，然后将 c 添加至栈顶
  • 遍历了字母 c 后，注意要将 count 数组中维护的 c 的剩余出现次数 - 1，并修改 exist 数组来标记栈中已存在字母 c

最后将栈中从栈底到栈顶的所有字母拼接成字符串，然后将结果返回即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        boolean[] exist = new boolean[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        Deque<Character> deque = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (!exist[c - 'a']) {
                if (!deque.isEmpty()) {
                    while (!deque.isEmpty() && deque.peekLast() > c && count[deque.peekLast() - 'a'] > 0) {
                        char ch = deque.removeLast();
                        exist[ch - 'a'] = false;
                    }
                }
                deque.addLast(c);
                exist[c - 'a'] = true;
            }
            count[c - 'a']--;
        }
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append(deque.removeFirst());
        }
        return sb.toString();
    }
}