当前位置：首页 > news >正文

LeetCode题练习与总结：去除重复字母--316

news 2025/6/8 11:14:58

一、题目描述

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

示例 1：

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

示例 2：

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

提示：

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

二、解题思路

遍历字符串s，使用一个数组count来记录每个字符出现的次数，因为字符串只包含小写字母，所以数组大小为26。
使用一个布尔数组visited来记录字符是否已经在结果字符串中。
使用一个字符栈stack来维护当前结果字符串，保证字典序最小。
遍历字符串s，对于每个字符：
- 将该字符的出现次数减一。
- 如果该字符已经在栈中，则跳过。
- 如果栈不为空，且栈顶元素大于当前字符，并且栈顶元素在后续还会出现，则将栈顶元素弹出，并将visited对应的值设为false。
- 将当前字符入栈，并将visited对应的值设为true。
将栈中的字符依次弹出并拼接到结果字符串中。

三、具体代码

import java.util.Stack;class Solution {public String removeDuplicateLetters(String s) {int[] count = new int[26]; // 记录每个字符出现的次数boolean[] visited = new boolean[26]; // 记录字符是否已经在栈中Stack<Character> stack = new Stack<>(); // 维护结果字符串的栈// 统计每个字符的出现次数for (char c : s.toCharArray()) {count[c - 'a']++;}// 遍历字符串for (char c : s.toCharArray()) {// 当前字符出现次数减一count[c - 'a']--;// 如果字符已经在栈中，则跳过if (visited[c - 'a']) {continue;}// 保证字典序最小while (!stack.isEmpty() && stack.peek() > c && count[stack.peek() - 'a'] > 0) {visited[stack.pop() - 'a'] = false;}// 当前字符入栈stack.push(c);visited[c - 'a'] = true;}// 构建结果字符串StringBuilder sb = new StringBuilder();while (!stack.isEmpty()) {sb.append(stack.pop());}return sb.reverse().toString();}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

统计每个字符出现次数的循环：这个循环遍历了字符串s中的所有字符一次，所以时间复杂度是O(n)，其中n是字符串s的长度。
遍历字符串s的循环：同样地，这个循环也遍历了字符串s中的所有字符一次，但是每次循环内部可能还会执行一个while循环。
while循环：在每次外层循环中，while循环可能会执行多次，但是每个字符最多只会被弹出一次（因为一旦弹出，它的visited状态会被设置为false，就不会再被弹出）。因此，while循环中每个字符最多只会被处理一次。在最坏的情况下，如果所有字符都按照降序排列，那么每个字符都会被弹出并重新入栈，所以while循环的总体时间复杂度是O(n)。

综合上述步骤，总的时间复杂度是O(n) + O(n) + O(n) = O(n)。

2. 空间复杂度

count数组：这个数组的大小是固定的，为26，因为字符串s只包含小写英文字母，所以空间复杂度是O(1)。
visited数组：同样地，这个数组的大小也是固定的，为26，所以空间复杂度是O(1)。
栈stack：在最坏的情况下，栈中可能会包含所有不同的字符，即26个字符，所以空间复杂度是O(1)。
StringBuilder：在构建最终结果字符串时，StringBuilder中最多会包含26个字符，所以空间复杂度是O(1)。

综上所述，总的空间复杂度是O(1) + O(1) + O(1) + O(1) = O(1)。

五、总结知识点

数据结构：
- 数组：count数组用于记录每个字符出现的次数，而visited数组用于记录字符是否已经在栈中。
- 栈：Stack类用于实现栈的数据结构，用于维护结果字符串的字符顺序。
字符操作：
- 字符与整数的转换：通过c - 'a'将字符转换为整数，以便在数组中进行索引操作。
- 字符串与字符数组的转换：使用toCharArray()方法将字符串转换为字符数组。
循环与条件判断：
- for-each循环：用于遍历字符串中的每个字符。
- while循环：用于在栈不为空的情况下，确保栈顶元素小于当前字符，并且栈顶元素在后续还会出现时，将其弹出。
逻辑控制：
- continue语句：用于跳过已经存在于栈中的字符的后续处理。
- 布尔数组：用于标记某个字符是否已经处理过。
字符串构建：
- StringBuilder类：用于构建最终的字符串结果，因为它比使用字符串连接操作符+更高效。
算法思想：
- 贪心算法：通过维护一个栈来确保结果字符串的字典序最小，每次只保留最小的字符在栈顶。
- 计数与标记：通过计数数组来记录字符出现的次数，通过标记数组来记录字符是否已经入栈。