当前位置: 首页 > article >正文

leetcode中“辅助栈”类题目和“单调栈”类题目的异同

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();
    }
}

http://www.kler.cn/a/145340.html

相关文章:

  • 基于Python的人工智能患者风险评估预测模型构建与应用研究(下)
  • AI编译器之——为什么大模型需要Relax?
  • 性能优化2-删除无效引用
  • 【每日一A】2015NOIP真题 (二分+贪心) python
  • Nginx前端后端共用一个域名如何配置
  • 【Jave全栈】Java与JavaScript比较
  • Redis当中的BitMap,实现github打卡功能
  • 嵌入式设备摄像头基础知识
  • Python算法——霍夫曼编码树
  • tensorflow和pytorch的联系与区别
  • 基于PyQT5的图像分类网络训练平台
  • 鸿蒙开发报错:agconnect sdk not initialized. please call initialize()【BUG已解决】
  • Go 异常处理流程
  • 第六题-红和蓝【第六届传智杯程序设计挑战赛解题分析详解复盘】(JavaPythonC++实现)
  • 《数据结构与算法之美》读书笔记2
  • c语言实现10进制转16进制
  • kotlin 内置函数对数组进行各种操作
  • Day02嵌入式---按键控灯
  • 【超强笔记软件】Obsidian实现免费无限流量无套路云同步
  • 2023.11.25 关于 MyBatis 的配置与使用
  • RAID磁盘阵列
  • 二十三种设计模式全面解析-深入探讨状态模式的高级应用技术:释放对象行为的无限可能
  • 深入学习pytorch笔记
  • 大数据-之LibrA数据库系统告警处理(ALM-37002 MPPDB实例连接数超限)
  • 公司人事管理系统
  • 企业海外分部,如何实现安全稳定的跨境网络互连?