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

**去除重复字母**

**力扣**

**贪心 + 队列 JAVA**

###问题描述给定一个字符串 `s`，要求从中去除所有出现次数超过一次的字母，并返回剩余的字母组成的新字符串。

### 示例* 输入：`"aabbbcc"`
* 输出：`"abc"`

### 思路本题可以使用贪心算法和队列数据结构来解决。首先，我们需要对输入字符串进行排序，以便于后续的处理。然后，我们创建一个队列来存储结果中的字母。

### JAVA代码实现

javaimport java.util.*;

public class Solution {
 public String removeDuplicateLetters(String s) {
 // 对输入字符串进行排序 char[] chars = s.toCharArray();
 Arrays.sort(chars);

 // 创建一个队列来存储结果中的字母 Deque stack = new ArrayDeque<>();

 for (char c : chars) {
 // 如果当前字符已经在栈中，则跳过 if (stack.contains(c)) continue;

 // 如果栈不为空，并且当前字符小于栈顶元素，则弹出栈顶元素 while (!stack.isEmpty() && stack.peekBack() > c) {
 stack.pollLast();
 }

 // 将当前字符压入栈中 stack.push(c);
 }

 // 将栈中的字母组合成新字符串并返回 StringBuilder sb = new StringBuilder();
 for (Character c : stack) {
 sb.append(c);
 }
 return sb.toString();
 }

 public static void main(String[] args) {
 Solution solution = new Solution();
 System.out.println(solution.removeDuplicateLetters("aabbbcc")); // "abc"
 }
}

###代码注释* 首先，我们对输入字符串 `s` 进行排序，以便于后续的处理。
* 然后，我们创建一个队列来存储结果中的字母。我们使用 `Deque` 接口和 `ArrayDeque` 类来实现这个队列。
* 在遍历排序后的字符数组时，我们首先检查当前字符是否已经在栈中。如果是，则跳过当前字符。
* 如果栈不为空，并且当前字符小于栈顶元素，则弹出栈顶元素。这是因为我们希望栈中的字母都是最小的，且没有重复的字母。
* 最后，我们将栈中的字母组合成新字符串并返回。

### 时间复杂度本题的时间复杂度为 O(n)，其中 n 是输入字符串 `s` 的长度。我们首先对输入字符串进行排序，这个操作需要 O(n log n) 的时间复杂度。但是，我们可以使用快速排序或其他高效的排序算法来降低这个时间复杂度。

在遍历排序后的字符数组时，我们执行一些常数时间复杂度的操作，包括检查当前字符是否已经在栈中、弹出栈顶元素等。这些操作的总时间复杂度为 O(n)。

因此，整个算法的时间复杂度为 O(n log n + n) = O(n)，忽略了对输入字符串进行排序所需的额外时间复杂度。

### 空间复杂度本题的空间复杂度为 O(n)，其中 n 是输入字符串 `s` 的长度。我们使用一个队列来存储结果中的字母，队列中可能包含 n 个元素。

因此，整个算法的空间复杂度为 O(n)。