[刷题防痴呆] 0316 - 去除重复字母 (Remove Du

题目地址

https://leetcode.com/problems/remove-duplicate-letters/description/

题目描述

316. Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"
Output: "abc"
Example 2:

Input: "cbacdcbc"
Output: "acdb"
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

思路

• 重点在两点: 1.保持原来的字母顺序不变. 2.去重后的顺序是所有结果里字典序里最小.
• 记录下每个字母出现的次数. 理论上字母序比较大的字母, 如果多次出现, 则保留更靠后的那一个.
• 用visited记录站内存放的字母.
• 扫描字符串, 对比扫描到的当前字母和栈顶的字母, 如果栈顶的字母序更大, 并且栈顶字母在之后的扫描中还会出现, 则把栈顶字母从栈中移除. 直到把栈中所有大于当前扫描字母, 并且之后还会再出现的字母都移除后, 再在栈中放入当前字母.
• 最后栈内从栈底到栈顶的顺序既是结果.

关键点

• 用一个栈来维护答案, 从左往右扫描字符串, 当栈顶元素字典序小于当前扫描的字符, 并且栈顶元素在s未被扫描到的部分中还有出现时, 栈顶元素出栈, 并继续比较新的栈顶元素与当前字符字符, 重复上面的过程, 直到不符合上述条件时, 再让当前字符入栈.
• 因为已知有26个字符, 使用int[]来代替hashmap, 使用boolean[]来代替hashset.

代码

• 语言支持：Java

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] lastIndex = new int[26];
        char[] sc = s.toCharArray();
        int n = sc.length;
        for (int i = 0; i < n; i++) {
            lastIndex[sc[i] - 'a'] = i;
        }
        Deque<Character> stack = new ArrayDeque<>();
        boolean[] visited = new boolean[26];
        for (int i = 0; i < n; i++) {
            char c = sc[i];
            if (visited[c - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > c && lastIndex[stack.peek() - 'a'] > i) {
                char pop = stack.pop();
                visited[pop - 'a'] = false;
            }
            stack.push(c);
            visited[c - 'a'] = true;
        }

        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}