algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/yi-dao-shu-ed782/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/yi-dao-shu-ed782/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 1081. Smal...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/yi-dao-shu-ed782/

[shiboys]

确实比较复杂

[EurekaT1me]

栈或者双端队列都可以实现

[HCWGH]

数组模拟单调栈，bit位标记被选中，极致存储空间压缩

class Solution {
    public String smallestSubsequence(String s) {
        //记录每个字符最后一次出现的位置
        int[] chArr = new int[26];
        //selected的bit位标记字符是否被选中 ，count不重复的字符个数,index栈索引
        int selected = 0, count = 0, index = -1;
        for (int i = s.length() - 1; i >= 0; i--) {
            //每个字符最后一次出现的位置
            char ch = s.charAt(i);
            if (chArr[ch - 'a'] == 0) {
                count++;
                chArr[ch - 'a'] = i;
            }
        }
        //数组模拟栈
        char[] stack = new char[count];
        for (int i = 0; i < s.length(); i++) {
            int chIndex = s.charAt(i) - 'a';
            //如果字符已被选过直接进入下一次循环
            if (((selected >> chIndex) & 1) == 1) continue;
            //栈顶元素大于当前元素，且栈顶元素在后续还会出现，则出栈。chArr[stack[index] - 'a'] > i表示栈顶元素最后一次出现的索引大于i
            while (index >= 0 && stack[index] > s.charAt(i) && chArr[stack[index] - 'a'] > i) {
                //出栈同时栈顶元素，被选中标记复位
                selected ^= (1 << stack[index] - 'a');
                index--;
            }
            //放入栈顶，同时标记为被选中
            stack[++index] = s.charAt(i);
            selected |= 1 << chIndex;
        }
        return String.valueOf(stack);
    }
}