LeetCode-316. 去除重复字母&&1081.不同字符的最小子序列(Java实现)

灰太狼 2022-12-29 06:54 168阅读 0赞

> **LeetCode题号：**[316. 去除重复字母][316.]
> 
> 给你一个字符串 `s` ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 **返回结果的字典序最小**（要求不能打乱其他字符的相对位置）。
> 
> **示例 1：**
> 
>     输入：s = "bcabc"
>     输出："abc"
> 
> 注意：该题与 [1081. 不同字符的最小子序列][1081.] 相同
> 
> **思路：**
> 
> 统计字符出现次数，遍历字符串，当前字符出现次数-1；当前字符不在栈中（目的：去重，如abcabc的第二个a）；栈顶字符 > 当前字符（目的：字典序最小。贪心策略：字符越小越前）；栈顶字符后面还有出现（目的：字符至少出现一次。没有出现不能删）；弹出，即删。重复上面的判断，直到条件不成立；即：数组越界 或 栈顶字符 < 当前字符 或 >，但后面没有该字符；

public String removeDuplicateLetters(String s) {
            LinkedList<Character> deque = new LinkedList<>();
            int[] count = new int[26];
            boolean[]exists = new boolean[26];
            // 初始化
            for(char ch : s.toCharArray()){
                count[ch - 'a']++;
            }
            // 遍历s并入栈
            for (int i = 0; i < s.length(); i++) {
                char temp = s.charAt(i);
                //判断该位置字母没有在栈中出现过
                if (!exists[temp - 'a']){
                    //栈不为空 && 栈顶元素字典序列靠后 && 栈顶元素还有剩余出现次数
                    while (!deque.isEmpty() && deque.getLast() > temp && count[deque.getLast() - 'a'] > 0){
                        // 修改出现状态
                        exists[deque.getLast() - 'a'] = false;
                        // 栈顶元素弹出。替换
                        deque.removeLast();
                    }
                    // 该位置的字母压栈
                    deque.add(temp);
                    // 修改出现状态
                    exists[temp - 'a'] = true;
                }
                // 遍历过的字母出现次数减一
                count[temp - 'a']--;
            }
            //返回栈中元素
            StringBuilder res = new StringBuilder();
            for(char ch : deque){
                res.append(ch);
            }
            return res.toString();
        }

--------------------

**往期回顾：**

【1】[LeetCode-164. 最大间距(Java实现)][LeetCode-164. _Java]

【2】[LeetCode-1370. 上升下降字符串(Java实现)][LeetCode-1370. _Java]

【3】[LeetCode-454. 四数相加 II(Java实现)][LeetCode-454. _ II_Java]

--------------------

> ❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ 
> 
> ❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
> 
> ❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
> 
> ❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)

[316.]: https://leetcode-cn.com/problems/remove-duplicate-letters/
[1081.]: https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/
[LeetCode-164. _Java]: https://blog.csdn.net/weixin_43970743/article/details/110192475
[LeetCode-1370. _Java]: https://blog.csdn.net/weixin_43970743/article/details/110189600
[LeetCode-454. _ II_Java]: https://blog.csdn.net/weixin_43970743/article/details/110223124