*LEETCODE 316. 去除重复字母
1. 问题
给你一个字符串 s
,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入:s = "bcabc"
输出:"abc"
示例 2:
输入:s = "cbacdcbc"
输出:"acdb"
提示:
1 <= s.length <= 104
s
由小写英文字母组成
2. 标签
贪心
栈
字符串
3. 解法 - 贪心 栈
3.1 Java
class Solution {
public String removeDuplicateLetters(String s) {
// 记录每个字符是否出现在栈中
boolean[] inStack = new boolean[26];
// 使用数组计算字符串中每个字符出现的次数
int[] num = new int[26];
for (int i = 0; i < s.length(); i++) {
num[s.charAt(i) - 'a']++;
}
// 栈
StringBuffer stack = new StringBuffer();
// 遍历字符串
for (int i = 0; i < s.length(); i++) {
// 当前遍历字符
char ch = s.charAt(i);
// 如果当前字符不在栈中
if (!inStack[ch - 'a']) {
// 给定一个字符串 s,如何去掉其中的一个字符 ch,使得得到的字符串字典序最小呢?
// 答案是:找出最小的满足 s[i]>s[i+1] 的下标 i,并去除字符 s[i]。该字符即为「关键字符」
// 如果栈不为空,且栈顶的字符大于当前字符,说明栈顶字符就是「关键字符」
while (stack.length() > 0 && stack.charAt(stack.length() - 1) > ch) {
// 如果后面还有关键字符,就可以放心让此时栈顶的关键字符出栈
if (num[stack.charAt(stack.length() - 1) - 'a'] > 0) {
inStack[stack.charAt(stack.length() - 1) - 'a'] = false;
stack.deleteCharAt(stack.length() - 1);
} else {
// 如果后面没有关键字符了,就留下它
break;
}
}
// 处理好了关键字符后,就来处理当前字符
// 把当前字符放入栈中
stack.append(ch);
inStack[ch - 'a'] = true;
}
// 如果当前字符已经在栈中了,就不要再放进去了,我们的目标就是去除重复字符
num[ch - 'a'] -= 1;
}
// 此时栈中剩下的就是去除了重复字符的字符串
return stack.toString();
}
}
3.2 复杂度分析
时间复杂度
O(n)
:其中 n 是字符串长度,每个字符最多只会入栈、出栈各一次。空间复杂度
O(m)
:其中 m 为字符集合的总数。本题中字符均为小写字母,所以 m=26。由于栈中的字符不能重复,因此栈中最多只能有 m 个字符,另外需要维护两个数组,分别记录每个字符是否出现在栈中以及每个字符的剩余数量。
4. 参考
最后更新于
这有帮助吗?