LeetCode-316. 去除重复字母(hard且重要)
题目描述:
给你一个字符串 s
,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
PS:所谓字典序最小,即要求字母最大限度按照字母表排序的顺序排序。
字典序:字典序是 按照单词出现在字典中的顺序 比较两个字符串的方法。
首先比较第 1 个字符的 ASCII 码:
如果不同,则第 1 个字符 ASCII 码较小的字符,整体字典序更靠前;
如果相同,则继续比较第 2 个字符,……
如此继续,比较整个字符串的大小。
示例 1:
输入:s = "bcabc"
输出:
"abc"
示例 2:
输入:s = "cbacdcbc"
输出:"acdb"
思路分析:
栈+贪心算法
1.题目要求字典排序, 则结果中第一个字母的字典序靠前的优先级最高---贪心
azzzzzz 比
baaaaaa 的字典序列更靠前
2.因为不能打乱相对位置---即输入中排在输出第一个字母位置前的字母都不能出现,所以要在保证每个字母至少出现一次的前提下再考虑字典序排列
若输入为 bacc
则输出 ac 不合法
不能以 a 作为第一位因为这样会导致 bacc 中
a 之前只出现一次的 b 失效
3.根据第1点可以考虑使用单调栈来保证字典序排列,根据第2点我们给元素出栈时加上限制条件,只有在栈顶元素字典序靠后,==且在之后还有出现次数才弹出栈==.同时压栈时应该注意栈中没有出现过该元素才能压栈.
若输入为bcacc
1. b 入栈
2. c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
3. a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素.
元素 c 因为在之后还有 至少一次 出现次数,所以这里可以弹出.
元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.
4. c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
5. c 入栈时栈中已经出现过c,跳过该元素
输出结果为 bac
4.需要的存储结构
根据思路首先需要一个栈结构,由于最终输出结果是先进先出,我们使用双向队列来模拟栈的操作.
弹出栈顶元素时需要知道该字母剩余出现次数,可以用一个哈希表统计字母出现次数,这里元素都是小写字母,可以使用长度26的int数组代替
压栈时还需要一个哈希表统计栈中是否出现过该字母,同上可以用长度26的boolean型数组代替
5.伪代码
// 声明变量
for{ // 遍历字符串s
// 初始化字母出现次数哈希表
}
for{ // 遍历字符串s
if(该位置字母没有在栈中出现过){
while(栈不为空 && 栈顶元素字典序列靠后 && 栈顶元素还有剩余出现次数){
// 修改出现状态
// 栈顶元素弹出
}
// 该位置的字母压栈
// 修改出现状态
}
// 遍历过的字母出现次数减一
}
// 返回栈中元素
class solution{
public String removeDuplicateLetters(String s){
int len=s.length();
char[] chararray=s.toCharArray();
boolean[] visited=new boolean[26]; //记录某一个字符是否在栈中出现
Deque<Character> stack=new ArrayDeque<>();
int[] lastIndex=new int[26];
for(int i=0;i<len;i++){
lastIndex[chararray[i]-'a']=i;//记录每个元素最后一次出现的位置
}
for(int i=0;i<len;i++){
if(visited[chararray[i]-'a']{
continue; //如果出现舍弃当前字符
}
//当前字符在栈顶元素之前,且栈顶元素在后面还有
while(!stack.isEmpty() && stack.peekLast()>chararray[i]&&lastIndex[stack.peekLast()-'a']>i){
Char c=stack.removLast(); //移除栈顶元素
visited[c-'a']=false;//表示该字符没有在栈中出现
}
stack.addLast(chararray[i]);
visited[chararray[i]-'a']=true;
}
StringBuilder stringbuilder=new StringBuilder();
for(char c:stack){
stringbuilder.append(c);
}
return stringbuilder.toString();
}
}
时间复杂度:O(N),其中 NN 为字符串长度。代码中虽然有双重循环,但是每个字符至多只会入栈、出栈各一次。
空间复杂度:O(∣Σ∣),其中Σ 为字符集合,本题中字符均为小写字母,所以∣Σ∣=26。由于栈中的字符不能重复,因此栈中最多只能有∣Σ∣ 个字符,另外需要维护两个数组,分别记录每个字符是否出现在栈中以及每个字符的剩余数量。
文章来源: blog.csdn.net,作者:小小谢先生,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/xiewenrui1996/article/details/113559211
- 点赞
- 收藏
- 关注作者
评论(0)