去除重复字母（力扣）贪心 + 队列 JAVA

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

示例 1：

输入：s = “bcabc”
输出：“abc”

示例 2：

输入：s = “cbacdcbc”
输出：“acdb”

提示：

1 <= s.length <= 10^4
s 由小写英文字母组成

解题思路：

1、大于O(n ^ 2)时间复杂度的算法会超时

2、由于要输出字典序最小的排列，所以字典序越小的字符就我设法让其排在前面，这就是贪心思维

3、需要栈辅助，即栈顶元素比添加进来的元素大，那么设法消掉此栈顶元素

4、需要index数组保留字符最后一次出现的位置，以便删掉栈顶元素使用

5、需要boolean类型数组判断新添元素是否在栈内存在

代码：

class Solution {public String removeDuplicateLetters(String s) {char a[] = s.toCharArray();int len = a.length;int index[] = new int [26]; for(int i = 0; i < len; i ++) index[a[i] - 'a'] = i;//记录每个字母最后出现的位置；boolean check[] = new boolean [26];Deque<Character> stack = new ArrayDeque<>();for(int i = 0; i < len; i ++) {if(!check[a[i] - 'a']) {//如果栈内没有，就选择添加while(!stack.isEmpty() && stack.peekLast() > a[i] && index[stack.peekLast() - 'a'] > i) {//如果添加的元素比栈顶小char c = stack.removeLast();check[c - 'a'] = false;}stack.add(a[i]);check[a[i] - 'a'] = true;}}StringBuffer s1 = new StringBuffer();for(char d : stack) s1.append(d);return s1.toString();}
}