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

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

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

示例 1：

输入：s = "bcabc"
输出："abc"
示例 2：

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

运行结果


解题思路
利用栈记录结果
去重的入栈：已入栈跳过。当出现栈顶元素大于当前元素时判断，如果后续还有则出栈，后续再入，否则跳过
所以需要辅助数组来记录是否已经入栈，以及后续还有几个
26的数组是存字母到a的距离
256是直接存字母的ascll码
时间换空间
java代码

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] count=new int[26];//记录字符数目-26个英文字母
        boolean[] inStack=new boolean[26];//记录是否入栈
        Stack<Character> stack=new Stack<>();
        char[] chars=s.toCharArray();
        //记录字母的数目
        for(char c:chars){
            count[c-'a']++;
        }
        for(char c : chars){
            //数目减一
            count[c-'a']--;
            //已有则去重
            if(inStack[c-'a']) continue;
            //栈顶较小时
            while( !stack.isEmpty() && stack.peek() > c){
                //后续没有则跳出。必须有，不然会死循环
                if(count[stack.peek() - 'a']==0) break;
                //后续还有则弹出
                inStack[stack.pop()-'a']=false;
            }
            //入栈，改标志位
            stack.push(c);
            inStack[c-'a']=true;
        }
        //记录结果集
        StringBuffer sb=new StringBuffer();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

class Solution {
    public String smallestSubsequence(String s) {
        int[] count=new int[256];
        boolean[] instack=new boolean[256];
        Stack<Character> stk=new Stack<>();
        char[] chars=s.toCharArray();
        //记录字母的数目
        for(char c: chars){
            count[c]++;
        }
        for(char c : chars){
            //遍历减1
            count[c]--;
            //已入栈去重
            if(instack[c]) continue;
            //若栈顶过大
            while( !stk.isEmpty() && stk.peek() > c){
                //若后续没有则跳过
                if(count[stk.peek()]==0) break;
                //否则出栈，改标志
                instack[stk.pop()]=false;
            }
            //入栈改标志
            stk.push(c);
            instack[c]=true;
        }
        //记录结果
        StringBuilder sb=new StringBuilder();
        while(!stk.isEmpty()){
            sb.append(stk.pop());
        }
        return sb.reverse().toString();
    }
}