题目描述
难度 - 中等
leetcode316. 去除重复字母
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入:s = “bcabc”
输出:“abc”
示例 2:
输入:s = “cbacdcbc”
输出:“acdb”
提示:
1 <= s.length <= 1e4
s 由小写英文字母组成
单调栈
题目要求总共有三点:
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。
根据要求三,我们就能想到这题可以用单调栈,用单调栈来保证字典序排列。
要求一,我们要去重,因此要加上出栈的条件。
只有在栈顶元素字典序靠后,且在之后还有出现次数才弹出栈.同时压栈时应该注意栈中没有出现过该元素才能压栈.
若输入为bcacc
- b 入栈
- c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
- a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素.
元素 c 因为在之后还有 至少一次 出现次数,所以这里可以弹出.
元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.- c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
- 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,去存储元素,最后保留的结果,就是要的答案
代码演示:文章来源:https://www.toymoban.com/news/detail-685992.html
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. 分割数组的最大值文章来源地址https://www.toymoban.com/news/detail-685992.html
到了这里,关于leetcode316. 去除重复字母(单调栈 - java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!