java数据结构与算法刷题-----LeetCode155. 最小栈

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

在这里插入图片描述

1. 法一:使用辅助最小栈

解题思路:时间复杂度O(1),空间复杂度O(n)
  1. 我们出栈和入栈时,要同步维护一个最小值栈
  2. 最小值栈主要保存当前最小值
  3. 这样,我们就可以实时获取当前栈中最小值
  4. 图解如下:
  1. 入栈-2,则栈顶元素为-2,当前最小值也是-2
    在这里插入图片描述
  2. 入栈0,此时栈顶为0,但是最小值还是-2,所以最小栈依然入栈-2
    在这里插入图片描述
  3. 入栈-3,当前最小值为-2,但是-3比-2小,所以最小栈入栈-3
    在这里插入图片描述
  4. 此时执行getMin()操作获取当前最小值,那么直接获取最小栈的栈顶-3.
  5. 此时执行出栈操作,那么栈顶元素为-3. 同样的,最小栈也需要出栈
    在这里插入图片描述
  6. 此时执行top操作,也就是获取栈顶元素,那么直接获取栈顶的0即可
  7. 再次执行getMin()获取最小值,那么直接获取最小栈的栈顶-2即可。
代码

在这里插入图片描述

class MinStack {
    //用链表模拟栈,作为栈存储的容器
    class ListNode {
        int val;//当前结点的值
        int min;//当前最小值。用一个变量模拟最小值栈
        ListNode next;//下一个结点

        public ListNode() {

        }

        public ListNode(int val, int min, ListNode next) {
            this.val = val;
            this.min = min;//min就是最小值栈
            this.next = next;
        }
    }

    ListNode head;//头结点

    public MinStack() {
        head = new ListNode();//头结点初始化
    }
    //入栈操作
    public void push(int val) {
        ListNode next = head.next, cur;//获取栈顶元素next,cur是当前要插入结点
        if (next != null && next.min < val) {//如果栈不为空
            //但是当前栈中最小值,比val更小,那么将当前结点入栈,但是最小值依然保存next.min
            cur = new ListNode(val, next.min, next);
        }
        else {//如果栈为空,直接入栈当前结点
            //或者栈不为空,但是当前结点的值更小的话,那么新的最小值为当前的val值
            cur = new ListNode(val, val, next);
        }
        head.next = cur;//头插法,实现先入后出
    }
    //出栈
    public void pop() {
        ListNode del = head.next;//取出栈顶元素
        head.next = del.next;//头结点指向新的栈顶元素
    }
    //获取栈顶元素的值
    public int top() {
        return head.next.val;
    }
    //获取最小值,就在栈顶元素的min变量中保存
    public int getMin() {
        return head.next.min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

1. 法二:使用差值

解题思路:时间复杂度O(1), 空间复杂度O(1)
  1. 用变量min保存当前栈中最小值,而入栈时,保存当前值与最小值的差值
  1. 初次入栈,最小值和入栈值相同,所以差值为0
    在这里插入图片描述
  2. 第二次入栈时,入栈0,与-2差值为0 - ( -2 ) = 2
    在这里插入图片描述
  3. 第3次入栈时,入-3,与-2的差值为 ( -3 ) - ( -2 ) = -1. 最小值更新为-3.我们发现如果遇到更小值,那么差值为负数,并且更新了最小值
    在这里插入图片描述
  4. 此时执行getMin()获取最小值,直接返回Min变量保存的-3即可
  5. 此时执行出栈操作,我们发现,栈顶元素为负数,说明他就是当前最小值,那么需要执行逆运算获取接下来的最小值。
  1. 获取时的式子是:当前值 - 最小值 = 入栈值,(-3) - (-2) = 1并令当前值-3成为新的最小值
  2. 则当前 , 需要出栈的元素值,就是当前最小值-3
  3. 而新的最小值需要逆运算得出,最小值 = 当前值(就是当前最小值-3) - 入栈值 = (-3) - (-1) = -2. 故,出栈后,新的最小值为-2
    在这里插入图片描述
  1. 此时执行top操作获取栈顶元素,也需要逆操作。
  1. 如果栈顶元素<=0说明,当前最小值就是栈顶元素
  2. 如果不是,那就是通过式子:入栈值 = 原来的值 - 最小值得到的
  3. 还原则需要:原来的值 = 入栈值+最小值 = 2 + (-2) = 0. 故当前栈顶元素为0.
  1. 此时执行getMin()操作,获取最小值,依然获取MIn保存的值-2即可。
代码

在这里插入图片描述

class MinStack {
    // 记录每个元素与【未压入】该元素时栈中最小元素的差值
    LinkedList<Long> stack;
    // 当前【已压入】栈中元素的最小值
    private long min;
    public MinStack() {
        stack = new LinkedList();//初始化栈
    }
    
    public void push(int val) {
        // 压入第一个元素
        if(stack.isEmpty()){//栈为空时
            min = val;//最小值就是当前值
            stack.addFirst(0L);//头插法,当前值和最小值相同,所以他俩的差值为0
            return;
        }
        // 栈不为空时,每次压入计算与min的差值后压入结果
        stack.push((long)val-min);
        // 更新min,保存更小的
        min = Math.min((long)val,min);
        // 上面两个语句是不能颠倒的!一定是先压入,在更新,因为min一定是当前栈中的最小值
    }
    
    public void pop() {
        long pop = stack.removeFirst();
        // 当弹出元素小于0时,说明弹出元素是当前栈中的最小值,要更新最小值
        if(pop<0){
            // 因为对于当前弹出的元素而言,计算压入栈中的值时,计算的是该元素与【未压入】该元素时
            // 栈中元素的最小值的差值,故弹出该元素后栈中的最小值就是未压入该元素时的最小值
            // 即当前元素的值(min)减去两者的差值
            long lastMin = min;
            min = lastMin - pop;
        }
        // 若大于等于0,不会对min有影响
    }
    
    public int top() {
        long peek = stack.peek();
        // 若当前栈顶小于等于0,说明最小值就是栈顶元素
        if(peek<=0) return (int)min;
        // 否则就是min+peek
        return (int)(min+peek);
    }
    
    public int getMin() {
        return (int)min;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/397402.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何搭建一个稳定的服务器集群?

服务器集群能够提供高效、可扩展的计算和存储资源&#xff0c;满足企业不断增长的业务需求。但是&#xff0c;如何搭建一个稳定的服务器集群呢&#xff1f;下面将从多个方面进行介绍。 一、需求分析 在搭建服务器集群之前&#xff0c;首先要进行需求分析&#xff0c;明确集群…

Vue26 内置标签 v-text v-html

实例 <!DOCTYPE html> <html><head><meta charset"UTF-8" /><title>v-text指令</title><!-- 引入Vue --><script type"text/javascript" src"../js/vue.js"></script></head><…

《最新出炉》系列初窥篇-Python+Playwright自动化测试-19-处理鼠标拖拽-中篇

1.简介 上一篇中&#xff0c;主要是介绍了拖拽的各种方法的理论知识以及实践&#xff0c;今天宏哥讲解和分享一下划取字段操作。例如&#xff1a;需要在一堆log字符中随机划取一段文字&#xff0c;然后右键选择摘取功能。 2.划取字段操作 划取字段操作就是在一段文字中随机选…

qt for python创建UI界面

现在很多库都有用到python,又想使用QT creater创作界面&#xff0c;来使用。 1.使用的版本 使用虚拟机安装Ubuntu22.04&#xff0c;Ubuntu使用命令行安装qt,默认安装的是QT5&#xff0c;不用来回调了&#xff0c;就用系统默认的吧&#xff0c;不然安装工具都要费不少事情。pyt…

新版Java面试专题视频教程——框架篇

新版Java面试专题视频教程——框架篇 框架篇 01-框架篇介绍02-Spring-单例bean是线程安全的吗03-Spring-AOP相关面试题04-Spring-事务失效的场景05-Spring-bean的生命周期5.1 BeanDefinition 06-Spring-bean的循环依赖(循环引用)6.1 一般对象的循环依…

Spring Cloud微服务网关Zuul动态路由配置优化和手动触发路由刷新

一、前文必看 Spring Cloud微服务网关Zuul动态路由配置。在前文中留了两个小坑。在本文将怕它给填了&#xff0c;所以前一篇文章建议看一下。 二、DynamicZuulRouteLocator小优化 在前文中提到&#xff0c;HeartbeatEvent事件会频繁触发&#xff0c;每次都需要去查询数据库。…

云HIS定义,云HIS系统源码,云HIS建设方法,云HIS发展机制

一、重新定义HIS&#xff1a; 传统HIS是基于局域网的医院信息系统&#xff0c;云HIS全称为基于云计算的医疗卫生信息系统&#xff08;Cloud-Based Healthcare Information System&#xff09;&#xff0c;是运用云计算、大数据、物联网等新兴信息技术&#xff0c;按照现代医疗卫…

http前生今世

HTTP/0.9&#xff0c;仅支持GET方法&#xff0c;并且响应中没有HTTP头信息&#xff0c;只有文档内容。 HTTP/1.0增加了对POST方法、状态码、HTTP头信息等的支持&#xff0c;这一版本也是广泛应用的历史性版本。 HTTP/1.1引入了持久连接&#xff08;Persistent Connections&…

照片去除多余人物的方法分享之三分钟教你怎么去除

在拍摄照片时&#xff0c;有时候会遇到照片中有多余的人物&#xff0c;这会影响照片的美观度和主题表达。去除照片中多余的人物&#xff0c;需要采用一些技巧和方法。本文将介绍几种常用的去除照片中多余人物的方法。 一、使用水印云软件去除多余人物 水印云是一款功能强大的图…

[转载]31省市数字经济发展规划(2024版)

近期&#xff0c;国家统计局、国家税务总局、工业和信息化部等部门先后在国新办新闻发布会上发布2023年发展成绩单&#xff0c;其中&#xff0c;数字经济核心产业频频出现在发展成绩单中。 我国数实融合加快推进。根据国家税务总局发布的数据&#xff0c;2023年我国数字经济核…

JAVA高并发——锁的优化

文章目录 1、减少锁持有时间2、减小锁粒度3、用读写分离锁来替换独占锁4、锁分离5、锁粗化 锁是最常用的同步方法之一。在高并发的环境下&#xff0c;激烈的锁竞争会导致程序的性能下降&#xff0c;因此我们有必要讨论一些有关锁的性能的问题&#xff0c;以及一些注意事项&…

vulhub中Apache Log4j Server 反序列化命令执行漏洞复现(CVE-2017-5645)

Apache Log4j是一个用于Java的日志记录库&#xff0c;其支持启动远程日志服务器。Apache Log4j 2.8.2之前的2.x版本中存在安全漏洞。攻击者可利用该漏洞执行任意代码。 1.我们使用ysoserial生成payload&#xff0c;然后直接发送给your-ip:4712端口即可。 java -jar ysoserial-…

微软和OpenAI将检查AI聊天记录,以寻找恶意账户

据国外媒体报道&#xff0c;大型科技公司及其附属的网络安全、人工智能产品很可能会推出类似的安全研究&#xff0c;尽管这会引起用户极度地隐私担忧。大型语言模型被要求提供情报机构信息&#xff0c;并用于帮助修复脚本错误和开发代码以侵入系统&#xff0c;这将很可能会成为…

01 Qt自定义风格控件的基本原则

目录 1.继承原生控件 2.组合原生控件 3.仿写原生控件 PS:后续将继续分享开发实践中各类自定义控件的方法、思路以及组件库 1.继承原生控件 关键字&#xff1a;继承、paintEvent 这里想说的是&#xff0c;Qt的Gui框架在封装原生控件的同时&#xff0c; 也为开发者提供了各…

AGI|一篇小白都能看懂的RAG入门介绍!

目录 一、前言 二、LLM主要存在的问题 三、RAG 是什么&#xff1f; 四、RAG中的搜索器 &#xff08;一&#xff09;主要的检索技术 &#xff08;二&#xff09;知识库索引技术 五、RAG目前遇到的问题和展望 一、前言 随着近几年AIGC的发展&#xff0c;不仅是大模型自身在…

Web3探索加密世界:什么是空投?

随着加密货币行业的迅速发展&#xff0c;人们开始听说各种各样的术语&#xff0c;其中包括"空投"&#xff08;Airdrop&#xff09;。在这里&#xff0c;我们将深入探讨什么是空投&#xff0c;以及它在加密世界中扮演的角色。 什么是空投&#xff1f; 空投是指在加密…

2.18号c++

1.菱形继承 1.1 概念 菱形继承又称为钻石继承&#xff0c;是由公共基类派生出多个中间子类&#xff0c;又由多个中间子类共同派生出汇聚子类。汇聚子类会得到多份中间子类从公共基类继承下来的数据成员&#xff0c;会造成空间浪费&#xff0c;没有必要。 问题&#xff1a; …

使用 GitHub Codespaces 加速 Elixir 开发环境工作速度

文章目录 前言加速 Elixir 开发环境参考 前言 使用 Elixir 开发点小玩意的时候&#xff0c;面对经常需要走外网下载依赖 (Elixir 的镜像站 UPYUN 使用有时候也经常抽风) 的时候&#xff0c;为了避免需要不断的进行网络代理配置&#xff0c;有想到之前经常使用 GitHub Codespac…

Spring两大核心思想:IOC和AOP

目录 IOC:控制反转 Ioc概念 Ioc的优点 Spring Ioc AOP:面向切面编程 AOP的优点 Spring AOP 1.添加依赖 2.核心概念 3.通知的类型 4.切点表达式 5.公共切点 pointCut 6.切面优先级 Order 7.使用自定义注解完成AOP的开发 Spring AOP实现有几种方式&#xff1f; S…

【C++】类与对象(构造函数、析构函数、拷贝构造函数、常引用)

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;http://t.csdnimg.cn/eCa5z 目录 类的6个默认成员函数 构造函数 特性 析构函数 特性 析构的顺序 拷贝构造函数 特性 常引用 前言 &…