LeetCode-316

题目链接：https://leetcode-cn.com/problems/remove-duplicate-letters

思路：这题应该考虑挑选，而不是删除。

代码：

public String removeDuplicateLetters(String s) {
    int[] map = new int[26]; // 字符频率统计表
    for (int i = 0; i < s.length(); i++) {
        map[s.charAt(i) - 'a']++;
    }
    char[] res = new char[26];
    int index = 0;
    int L = 0;
    int R = 0;
    while (R != s.length()) {
        // 如果当前字符是不再考虑的，直接跳过
        // 如果当前字符出现的次数减 1 之后，后面还能再出现，直接跳过
        if (map[s.charAt(R) - 'a'] == -1 || --map[s.charAt(R) - 'a'] > 0) {
            R++; // 只有 map[s.charAt(R) - 'a'] == 0 才会执行
        } else { // 当前字符需要考虑并且之后不会再出现
            // 在 s[L...R] 上所有需要考虑的字符中，找到 ASCII 码最小字符的位置
            int pick = -1;
            for (int i = L; i <= R; i++) {
                if (map[s.charAt(i) - 'a'] != -1 && (pick == -1 || s.charAt(i) < s.charAt(pick))) {
                    pick = i;
                }
            }
            // 把 ASCII 码最小的字符放到挑选结果中
            res[index++] = s.charAt(pick);
            // 在上一次循环中，也就是找到 R 位置的循环中，s[L...R] 范围内每种字符出现的次数都减少了
            // 需要把 s[pick + 1...R] 中每种字符的频率给加回来
            for (int i = pick + 1; i <= R; i++) {
                if (map[s.charAt(i) - 'a'] != -1) {
                    map[s.charAt(i) - 'a']++;
                }
            }
            // 选出 ASCII 码最小的字符，以后就不再考虑了
            map[s.charAt(pick) - 'a'] = -1;
            // 继续在 s.charAt[pick + 1......] 上重复这个过程
            L = pick + 1;
            R = L;
        }
    }
    return String.valueOf(res, 0, index);
}