316.去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的

字典序

最小（要求不能打乱其他字符的相对位置）。

示例 1：

输入：s = “bcabc”
输出：”abc”

示例 2：

输入：s = “cbacdcbc”
输出：”acdb”

提示：

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

题解：

class Solution {
    public String removeDuplicateLetters(String s) {
        // num数组保存每个字符出现的次数
        int[] num = new int[26];
        boolean[] compare = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            num[s.charAt(i) - 'a']++;
        }
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 如果compare数组中对应元素的布尔值为false则进去
            if (!compare[ch - 'a']) {
                // 如果要插入的字符字典序小于栈顶字符，则弹出栈顶字符，通过循环弹出，尽可能的保持栈底元素字典序最小
                while (stringBuffer.length() > 0 && ch < stringBuffer.charAt(stringBuffer.length() - 1)) {
                    // 如果num数组中栈顶字符的数量大于零就可以继续弹出，如果=0那不管是不是最小字典序都不能再弹出了
                    if (num[stringBuffer.charAt(stringBuffer.length() - 1) - 'a'] > 0) {
                        // 弹出栈顶元素要同时把元素对应在compare数组中的位置置回false
                        compare[stringBuffer.charAt(stringBuffer.length() - 1) - 'a'] = false;
                        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
                    } else {
                        break;
                    }
                }
                // 能入栈的元素都满足：要插入的字符字典序小于栈顶字符
                // 元素入栈且元素对应在compare数组中的位置要置为true
                compare[ch - 'a'] = true;
                stringBuffer.append(ch);
            }
            // 每次循环过后都要将对应字符数减一
            num[ch - 'a']--;
        }
        return stringBuffer.toString();
    }
}