🌕🌕 316. 去除重复字母 1081. 不同字符的最小子序列

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public String removeDuplicateLetters(String s) {
        // 思路：
        // 单调栈 
        // 依次遍历每个字符，判断该字符是否应该保留
        // 什么情况下保留？
        // 字符只出现过一次 || 字符比后一个保留的字符字典序小 || 栈空
        // 什么情况下不保留？
        // 字符前面已经出现过 || 字符比后一个保留的字符字典序大于等于 && 该字符之后还会出现
        char[] array = s.toCharArray();
        int len = array.length;
        int[] map = new int[26]; // 记录不同字符的出现次数
        boolean[] used = new boolean[26]; // 记录栈中是否存在该字符

        for(int i = 0; i < len; i ++) {
            int index = array[i] - 'a';
            map[index] ++;
        }
        // System.out.println(Arrays.toString(array));

        LinkedList<Character> stack = new LinkedList<>();
        for(int i = 0; i < len; i ++) {
            char c = array[i];
            int index = c - 'a';
            if(used[index]) {
                map[index] --;
                continue; // 前面已经出现过，跳
            }
            if(!stack.isEmpty() && c < stack.peek()) {
                // 判断是否弹出栈顶元素
                // 栈顶元素需后面还会有 才可弹出
                while(!stack.isEmpty() && c <= stack.peek() && map[stack.peek() - 'a'] > 0) {
                    char p = stack.pop();
                    used[p - 'a'] = false;
                }
            }
            stack.push(c);
            used[index] = true;
            map[index] --;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
        return sb.toString();
    }
}

---

输出