1 总结
1 栈中元素的特性
2 单调栈存在一次性连续删除多个栈顶的情况,但是普通的栈,一次只pop掉一个栈顶元素
2 LC1209. 删除字符串中的所有相邻重复项 II - 普通辅助栈
class Solution {
public String removeDuplicates(String s, int k) {
int n=s.length();
char[]cs=s.toCharArray();
StringBuilder res=new StringBuilder();
res.append(cs[0]);
Deque<Integer>st=new LinkedList<>();
st.addLast(1);
for(int i=1;i<n;i++){
res.append(cs[i]);
if(res.length()>1&&res.charAt(res.length()-1)==res.charAt(res.length()-2)){
st.addLast(st.pollLast()+1);
}else{
st.addLast(1);
}
if(st.peekLast()==k){
res.delete(res.length()-k,res.length());
st.pollLast();
}
}
return res.toString();
}
public String removeDuplicates2(String s, int k) {
int n=s.length();
char[]cs=s.toCharArray();
StringBuilder res=new StringBuilder();
res.append(cs[0]);
for(int i=1;i<n;i++){
if(!res.isEmpty()){
int cnt=1;
for(int j=0;j<Math.min(k-1, res.length());j++){
if(res.charAt(res.length()-1-j)==cs[i]){
cnt++;
}
}
if(cnt>=k){
int size=res.length();
res.delete(size-k+1,size);
}else{
res.append(cs[i]);
}
}else{
res.append(cs[i]);
}
}
return res.toString();
}
}
3 LC316 去除重复字母-单调栈
class Solution {
public String removeDuplicateLetters(String s) {
int n=s.length();
char[]cs=s.toCharArray();
StringBuilder res=new StringBuilder();
int[]set=new int[26];
boolean[]vis=new boolean[26];
for(int i=0;i<n;i++){
char c=cs[i];
set[c-'a']++;
}
for(int i=0;i<n;i++){
char c=cs[i];
int index=c-'a';
if(!vis[index]){
vis[index]=true;
while(res.length()>0&&res.charAt(res.length()-1)>c){
int tmp=res.charAt(res.length()-1)-'a';
if(set[tmp]==0){
break;
}
vis[tmp]=false;
res.deleteCharAt(res.length()-1);
}
res.append(c);
}
set[index]--;
}
return res.toString();
}
}