Leetcode 316 去除重复字母(单调栈)

朴灿烈づ我的快乐病毒、 2022-09-08 00:11 149阅读 0赞

## 题目重述 ##

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

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

### 示例 1： ###

输入：s = "bcabc"
    输出："abc"

### 示例 2： ###

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

### 提示： ###

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/remove-duplicate-letters  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

单调栈

## Java实现 ##

class Solution {
        
        public String removeDuplicateLetters(String s) {
        
            Stack<Character> stk = new Stack<>();
            // 记录每个字符的出现次数
            int[] count = new int[256];
            for (int i = 0; i < s.length(); i++) {
        
                count[s.charAt(i)]++;
            }
            // 标志字符是否在栈中
            boolean[] inStack = new boolean[256];
            for (char c : s.toCharArray()) {
        
                // 每遍历过一个字符，都将对应的计数减一
                count[c]--;
                // 如果已经在栈中，那么舍弃即可
                if (inStack[c]) continue;
    
                // 如果栈顶的字典序大于当前遍历的
                while (!stk.isEmpty() && stk.peek() > c) {
        
                    // 若之后不存在栈顶元素了，则停止 pop
                    if (count[stk.peek()] == 0) {
        
                        break;
                    }
                    // 若之后还有，则可以 pop
                    inStack[stk.pop()] = false;
                }
                stk.push(c);
                inStack[c] = true;
            }
            // 拼接栈中的字符串
            StringBuilder sb = new StringBuilder();
            while (!stk.empty()) {
        
                sb.append(stk.pop());
            }
            return sb.reverse().toString();
        }
    }