【贪心, 单调栈】去除重复字母

题目

316. 去除重复字母

1081. 不同字符的最小子序列

---

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

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

提示：

• 1 <= s.length <= 10^4
• s 由小写英文字母组成

**注意：**该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

解题

方法一：贪心 单调栈

思路

首先如果忽略「保证返回结果的字典序最小」这个条件，我们可以利用栈很容易的在不改变原字符相对顺序的情下给字符串去重：

class Solution {
    public String removeDuplicateLetters(String s) {
        Deque<Character> stk = new LinkedList<>();
        for (char ch : s.toCharArray()) {
            // 若栈中不存在该字符则把该字符入栈
            if (!stk.contains(ch)) stk.push(ch);
        }
        StringBuilder ans = new StringBuilder();
        // 把所有字符出栈并反向拼接
        while (!stk.isEmpty()) ans.insert(0, stk.pop());
        return ans.toString();
    }
}

那么现在问题就聚焦在了如何使返回结果的字典序最小，为了达成这个条件，我们应该尽可能的使所有字符按照字典序升序排列（abc 的字典序肯定比 cba 小嘛）。

我们只能删除重复字符，故想到：如果某个字符的字典序比前面字符的小且前面的字符正好在后面有重复，就可以删掉这个前面的字符，这样说可能不太看得懂，举个例子：

s = "bcabc" ，现在枚举到了 'a'，栈里的元素是：['c', 'b']，此时我们发现 'a' < 'c' 那么 a 理应向前移，但是 a 不能动怎么向前移？答案是发现 a 的后面还有重复的 c，于是把 a 前面的 c 删掉，这样 a 就变到了 c 的后面，接下来把 b 也以同样的理由删掉。

总结一下，在遍历字符的过程中遇到一个新字符，如果它比栈顶小，且在新字符的后面还有和栈顶一样的重复字符，就把栈顶的字符删除了，循环这么干直到 栈顶字符在后面没有重复字符了 或者 栈为空了 或者 新字符不比栈顶小了。

代码

class Solution {
    public String removeDuplicateLetters(String s) {
        Deque<Character> stk = new LinkedList<>();
        for (int i = 0; i < s.length(); ++i) {
            char curr = s.charAt(i);
            // 若栈中已存在相同字符则跳过
            if (stk.contains(curr)) continue;
            // 如果栈不为空且当前字符比栈顶字符小
            while (!stk.isEmpty() && stk.peek() > curr &&
            // 且在当前字符的后面还有与栈顶字符相同的重复字符
                s.indexOf(stk.peek(), i) != -1) stk.pop(); // 就删除栈顶字符
            stk.push(curr);
        }
        // 把所有字符出栈并反向拼接
        StringBuilder ans = new StringBuilder();
        while (!stk.isEmpty()) ans.insert(0, stk.pop());
        return ans.toString();
    }
}

stk.contains() 和 s.indexOf() 会明显拖慢该算法的运行速度，可以用一个布尔数组(has)来记录存在栈中的元素，一个整数数组(cnts)用于计数来判断后面是否还有重复字符，优化如下：

class Solution {
    public String removeDuplicateLetters(String s) {
        char[] chs = s.toCharArray();
        int[] cnts = new int[128];
        for (char ch : chs) ++cnts[ch];
        boolean[] has = new boolean[128];
        Deque<Character> stk = new LinkedList<>();
        for (char ch : chs) {
            --cnts[ch];
            if (has[ch]) continue;
            while (!stk.isEmpty() && stk.peek() > ch && cnts[stk.peek()] > 0)
                has[stk.pop()] = false;
            stk.push(ch);
            has[ch] = true;
        }
        StringBuilder ans = new StringBuilder();
        while (!stk.isEmpty()) ans.insert(0, stk.pop());
        return ans.toString();
    }
}

class Solution {
    int cnts[128];
    bool has[128];

public:
    string smallestSubsequence(string s) {
        for (char& ch : s) ++cnts[ch];
        stack<char> stk;
        for (char& ch : s) {
            --cnts[ch];
            if (has[ch]) continue;
            while (!stk.empty() && ch < stk.top() && cnts[stk.top()] > 0) {
                has[stk.top()] = false;
                stk.pop();
            }
            stk.push(ch);
            has[ch] = true;
        }
        string ans;
        while (!stk.empty()) ans.insert(0, 1, stk.top()), stk.pop();
        return ans;
    }
};