leetcode316. 去除重复字母(单调栈 - java)

题目描述

难度 - 中等
leetcode316. 去除重复字母

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

示例 1：
输入：s = “bcabc”
输出：“abc”

示例 2：
输入：s = “cbacdcbc”
输出：“acdb”

提示：
1 <= s.length <= 1e4
s 由小写英文字母组成

单调栈

题目要求总共有三点：
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。

根据要求三，我们就能想到这题可以用单调栈，用单调栈来保证字典序排列。
要求一，我们要去重，因此要加上出栈的条件。
只有在栈顶元素字典序靠后，且在之后还有出现次数才弹出栈.同时压栈时应该注意栈中没有出现过该元素才能压栈.

若输入为bcacc

1. b 入栈
2. c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
3. a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素.
   元素 c 因为在之后还有 至少一次 出现次数，所以这里可以弹出.
   元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.
4. c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
5. c 入栈时栈中已经出现过c,跳过该元素
   输出结果为 bac

代码演示

  String removeDuplicateLetters(String s) {Stack<Character> sta = new Stack<>();//只有小写字母，所以可以用26长度就可以了int[] count = new int[26];//统计每个字出现的次数，方便判断何时可以出栈for (char c : s.toCharArray()){count[c - 'a']++;}boolean[] inStack = new boolean[26];for (char c : s.toCharArray()){//每遍历一个元素，就把字符出现的次数减一count[c - 'a']--;if (inStack[c - 'a']){continue;}//出栈的三个条件//栈内元素不为null//当前元素字典序小于之前入栈的元素//并且保证后面还有要弹出的元素，如果后面没有了，就不能弹出while(!sta.isEmpty() && sta.peek() > c && count[sta.peek() - 'a'] > 0){inStack[sta.pop()  - 'a'] = false;}sta.push(c);inStack[c - 'a'] = true;}StringBuffer sb = new StringBuffer();while (!sta.isEmpty()){sb.append(sta.pop());}//栈先进后出，因此打印结果时要先逆序return sb.reverse().toString();}

进阶优化

上面解法中，我们用栈去保存元素，然后最后再倒进stringBuilder里，其实我们一开始就可以用StringBuilder,去存储元素，最后保留的结果，就是要的答案

代码演示：

 String removeDuplicateLetters(String s) {Stack<Character> sta = new Stack<>();StringBuffer sb = new StringBuffer();char[] chars = s.toCharArray();int[] count = new int[256];for (int i = 0; i < chars.length;i++){count[chars[i] - 'a']++;}boolean[] inStack = new boolean[26];for (char c : chars){count[c - 'a']--;if (inStack[c - 'a']){continue;}while(sb.length() > 0 && sb.charAt(sb.length() - 1) > c &&  count[sb.charAt(sb.length() - 1) - 'a'] > 0){inStack[sb.charAt(sb.length() - 1)  - 'a'] = false;sb.deleteCharAt(sb.length() - 1);}sb.append(c);inStack[c - 'a'] = true;}return sb.toString();}

上期经典

leetcode410. 分割数组的最大值