316. 去除重复字母

题目

原题 316. 去除重复字母

解题

题目中告知需要维持字典序并去除重复的字母，能够想到需要使用单调栈的思路，下面以 1 个具体例子分析问题：

给定字符串 s="cbacdcbc":

1. 'c' 直接入栈，当前栈中字符串为 "c"
2. 'b' 等待入栈，发现栈顶字符为 'c'，'c' > 'b' 并且 'b' 后面的这些字符中仍旧存在多个 'c' 字符，我们可以安全的把栈顶的 'c' 删除，于是栈变成了 "b"
3. 'a' 等待入栈，发现栈顶字符为 'b'，'b' > 'a' 并且 'a' 后面的这些字符中仍旧存在 'b' 字符，我们可以安全的删除栈顶 'b'，于是栈变成了 "a"
4. 'c' 等待入栈，发现栈顶字符是 'a'，'a' < 'c'，那么直接入栈，不需要维护单调栈，栈变成了 "ac"
5. 'd' 等待入栈，发现栈顶字符是 'c'，'c' < 'd'，那么直接入栈，不需要维护单调栈，栈变成了 "acd"
6. 'c' 等待入栈，栈中已经存在了字符 'c'，所以 'c' 不能够入栈，栈仍旧是 "acd"，等待入栈的 'c' 被丢弃
7. 'b' 等待入栈，发现栈顶字符是 'd'，'d' > 'b'，但是等待入栈的字符 'b' 后面并不存在任何字符 'd' 了，所以栈顶的 'd' 不能被删除，那么直接入栈，栈变成了 "acdb"
8. 'c' 等待入栈，栈中已经存在了字符 'c'，所以 'c' 不能够入栈，栈仍旧是 "acdb"，等待入栈的 'c' 被丢弃

根据分析问题的思路我们能够知道，需要使用一些变量去记录待入栈 c 字符的右侧任意字符剩余数量，某字符是否存在于栈中 关于如何理解这个字符剩余数量呢？下面是一些 tips：

• 初始化的 remains[] 记录了字符的总出现次数
• 一旦字符 c 被选择了，不管它是否入栈了（后续被入栈，或者被丢弃），都应该直接将这个字符剩余可用数量 remains[c] - 1

单调栈

public String removeDuplicateLetters(String s) {
    // 字符出现的次数
    int[] remains = new int[26];
    // 构造单调栈过程中，某个字符串是否在栈中存在
    boolean[] exists = new boolean[26];
    char[] chars = s.toCharArray();
    for (char c : chars) {
        remains[c - 'a']++;
    }
    StringBuilder sb = new StringBuilder();

    for (char c : chars) {
        // 选中了字符串 c, 从 remains 里面移除字符串 c
        remains[c - 'a']--;
        // 如果栈中已经存在字符 c, 就直接跳过
        if (exists[c - 'a'])
            continue;
        // 维护单调栈：栈顶字符 > 等待入栈的字符 c, 并且栈顶字符 remains>0, 说明可以被替换掉
        while (!sb.isEmpty() && sb.charAt(sb.length() - 1) > c && remains[sb.charAt(sb.length() - 1) - 'a'] > 0) {
            exists[sb.charAt(sb.length() - 1) - 'a'] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
        // 将字符 c 入栈
        sb.append(c);
        exists[c - 'a'] = true;
    }

    return sb.toString();
}