剑指 Offer 30. 包含min函数的栈
摘要
剑指 Offer 30. 包含min函数的栈
一、栈解析

package Stock;import java.util.Stack;/*** @Classname JZ30min函数栈* @Description TODO* @Date 2023/2/24 18:59* @Created by xjl*/
public class JZ30min函数栈 {/*** @description 最小栈的含义是每次从栈中获取的数据都是最小* @param: null* @date: 2023/2/24 19:00* @return:* @author: xjl*/class MinStack {Stack<Integer> stack;/** initialize your data structure here. */public MinStack() {stack = new Stack<>();}/*** @description 每次都是push两个数据当前数据和当前最小的数据* @param: x* @date: 2023/2/24 19:01* @return: void* @author: xjl*/public void push(int x) {if (stack.isEmpty()) {stack.add(x);stack.add(x);} else {int val=stack.peek();if (val > x) {stack.add(x);stack.add(x);} else {stack.add(x);stack.add(val);}}}/*** @description 每次都是弹出两个数据* @param:* @date: 2023/2/24 19:02* @return: void* @author: xjl*/public void pop() {stack.pop();stack.pop();}/*** @description 获取顶部的元素,就是获取第二个元素* @param:* @date: 2023/2/24 19:02* @return: int* @author: xjl*/public int top() {int min=stack.pop();int val=stack.pop();stack.push(val);stack.add(min);return val;}/*** @description 每次都是的获取最顶部的元素 * @param: * @date: 2023/2/24 19:03* @return: int* @author: xjl*/public int min() {return stack.peek();}}
}
复杂度分析
- 时间复杂度:对于题目中的所有操作,时间复杂度均为O(1)。因为栈的插入、删除与读取操作都是 O(1),我们定义的每个操作最多调用栈操作两次。
- 空间复杂度:O(2n),其中n为总操作数。最坏情况下,我们会连续插入n个元素,此时两个栈占用的空间为O(n)。
二、使用两个栈来实现
对于栈来说,如果一个元素a在入栈时,栈里有其它的元素b, c, d,那么无论这个栈在之后经历了什么操作,只要a在栈中,b, c, d 就一定在栈中,因为在 a 被弹出之前,b, c, d 不会被弹出。
因此,在操作过程中的任意一个时刻,只要栈顶的元素是 a,那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么,我们可以在每个元素a入栈时把当前栈的最小值m存储起来。在这之后无论何时,如果栈顶元素是 a,我们就可以直接返回存储的最小值m。

按照上面的思路,我们只需要设计一个数据结构,使得每个元素 a 与其相应的最小值 m 时刻保持对应。因此我们使用一个辅助栈,与元素栈同步插入与删除,用于存储与每个元素对应的最小值。
- 当一个元素要入栈时,我们取当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中;
- 当一个元素要出栈时,我们把辅助栈的栈顶元素也一并弹出;
- 在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中。
class MinStack {Deque<Integer> Stack;Deque<Integer> minStack;public MinStack() {Stack = new LinkedList<Integer>();minStack = new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void push(int x) {Stack.push(x);minStack.push(Math.min(minStack.peek(), x));}public void pop() {Stack.pop();minStack.pop();}public int top() {return Stack.peek();}public int min() {return minStack.peek();}
}
复杂度分析
- 时间复杂度:对于题目中的所有操作,时间复杂度均为O(1)。因为栈的插入、删除与读取操作都是 O(1),我们定义的每个操作最多调用栈操作两次。
- 空间复杂度:O(2n),其中n为总操作数。最坏情况下,我们会连续插入n个元素,此时两个栈占用的空间为O(n)。
博文参考
《leetcode》
相关文章:
剑指 Offer 30. 包含min函数的栈
摘要 剑指 Offer 30. 包含min函数的栈 一、栈解析 package Stock;import java.util.Stack;/*** Classname JZ30min函数栈* Description TODO* Date 2023/2/24 18:59* Created by xjl*/ public class JZ30min函数栈 {/*** description 最小栈的含义是每次从栈中获取的数据都是…...
stm32f407探索者开发板(二十二)——通用定时器基本原理讲解
文章目录一、三种定时器的区别二、通用定时器特点2.1 功能特点描述2.2 计数器模式三、通用定时器工作过程四、附一、三种定时器的区别 STM32F40x系列总共最多有14个定时器 三种(4)STM32定时器区别 二、通用定时器特点 2.1 功能特点描述 STM3 F4的通…...
cmake 入门三 常用变量和指令
cmake常用变量 一、cmake 变量引用的方式: 前面我们已经提到了,使用${}进行变量的引用。在IF 等语句中,是直接使用变量名而不通过${}取值 二,cmake 自定义变量的方式: 主要有隐式定义和显式定义两种,一…...
Linux基础命令-find搜索文件位置
文章目录 find 命令介绍 语法格式 命令基本参数 参考实例 1)在root/data目录下搜索*.txt的文件名 2)搜索一天以内最后修改时间的文件;并将文件删除 3)搜索777权限的文件 4)搜索一天之前变动的文件复制到test…...
获取浏览器硬件资源的媒体数据(拍照、录音、录频、屏幕共享)
目录一、window.navigator 对象包含有关访问者浏览器的信息取二、MediaDevices1.使用麦克风2.使用摄像头(和音频一样)3.拍照4.录屏三、MediaRecorder(录制,可录制音频视屏)一、window.navigator 对象包含有关访问者浏览器的信息取 <!DOCTYPE html>…...
Java入门教程||Java 日期时间||Java 正则表达式
Java 日期时间java.util包提供了Date类来封装当前的日期和时间。Date类提供两个构造函数来实例化Date对象。第一个构造函数使用当前日期和时间来初始化对象。Date( )第二个构造函数接收一个参数,该参数是从1970年1月1日起的毫秒数。Date(long millisec)Date对象创建…...
详解八大排序算法
文章目录前言排序算法插入排序直接插入排序:希尔排序(缩小增量排序)选择排序直接选择排序堆排序交换排序冒泡排序快速排序hoare版本挖坑法前后指针版本快速排序的非递归快速排序总结归并排序归并排序的非递归实现:计数排序排序算法复杂度及稳定性分析总结前言 本篇…...
python库streamlit学习笔记
什么是streamlit? Streamlit是一个免费的开源框架,用于快速构建和共享漂亮的机器学习和数据科学Web应用程序。它是一个基于Python的库,专为机器学习工程师设计。数据科学家或机器学习工程师不是网络开发人员,他们对花几周时间学习…...
C/C++开发,无可避免的内存管理(篇一)-约束好跳脱的内存
一、养成内存管理好习惯 1.1 养成动态对象创建、调用及释放好习惯 开发者手动接管内存分配时,必须处理这两个任务。分配原始内存时,必须在该内存中构造对象;在释放该内存之前,必须保证适当地撤销这些对象。如果你的项目是c项目&am…...
在React项目中引入字体文件并使用
一、背景 设计稿里某些文字所用的字体,系统默认不支持。 比如设计需要的这个字体:EmerlandRegular,即使在css里将文字字体设置为他们,实际效果也显示不出来。 二、现象及原因 1、样式 2、期待效果 3、实际效果 实际上是因为这个…...
STM32 CubeMX按键点灯
本文代码使用 HAL 库。 文章目录前言一、按键原理图二、CubeMX 创建工程三、代码讲解:1. GPIO的输入HAL库函数:2. 消抖:3. 详细代码四,实验现象:总结前言 我们继续讲解 stm32 f103,这篇文章将详细 为大家讲…...
2023链动2+1模式到底是什么?带你了解核心规则
2023链动21模式到底是什么?带你了解核心规则 2023-02-24 梦龙 大家好,我是你们熟悉而又陌生的好朋友梦龙,一个创业期的年轻人 传统的直销模式产品低价高卖,消费者难以接受。虽然直销省去了传统流通渠道的中间环节,但…...
【Java面试八股文宝典之基础篇】备战2023 查缺补漏 你越早准备 越早成功!!!——Day14
大家好,我是陶然同学,软件工程大三今年实习。认识我的朋友们知道,我是科班出身,学的还行,但是对面试掌握不够,所以我将用这100多天更新Java面试题🙃🙃。 不敢苟同,相信大…...
K8S篇-搭建kubenetes集群
安装环境 这里使用pve虚拟机搭建三台centos机器,搭建过程参考: Centos篇-Centos Minimal安装 此次安装硬件配置 CPU:2C 内存:2G 存储:64G 环境说明 操作系统:Centos 7.9 内核版本:6.2.0-1.el7.elrepo…...
文本生成图像简述4——扩散模型、自回归模型、生成对抗网络的对比调研
基于近年来图像处理和语言理解方面的技术突破,融合图像和文本处理的多模态任务获得了广泛的关注并取得了显著成功。 文本生成图像(text-to-image)是图像和文本处理的多模态任务的一项子任务,其根据给定文本生成符合描述的真实图像…...
财务共享建设,为什么需要电子影像系统?
某集团作为投资性集团公司,业务遍布全国20多个省市,控股公司200余家,业务范围涉及火电、供热、风电、天然气天然气、水务、铁路、港口、酒店、地产等20多个细分行业。 伴随着集团企业的快速发展,某集团在管理中面临“点多、面广、…...
「RISC-V Arch」SBI 规范解读(下)
第六章 定时器扩展(EID #0x54494D45"TIME") 这个定时器扩展取代了遗留定时器扩展(EID #0x00),并遵循 v0.2 中定义的调用规约。 6.1 函数:设置定时器(FID #0) struct sbi…...
Android framework socketpair
简述 在Linux中,socketpair函数可以用于创建一对相互连接的、通信域为AF_UNIX的套接字,其中一个套接字可用于读取,另一个套接字可用于写入。可以使用这对套接字在同一进程内进行进程间通信(IPC)。 以下是使用socketp…...
腾讯在海外游戏和短视频广告领域的新增长机会
来源:猛兽财经 作者:猛兽财经 腾讯(00700)的收入在过去几个季度一直在下降,部分原因是由于新冠疫情导致的经济放缓以及中国监管机构对大型科技公司的监管收紧导致游戏行业萎缩造成的。 然而,猛兽财经认为,这些不利因素…...
查找该学号学生的成绩。
从键盘输入某班学生某门课的成绩(每班人数最多不超过40人),当输入为负值时,表示输入结束,试编程从键盘任意输入一个学号,查找该学号学生的成绩。**输入格式要求:"%ld"(学号) "%l…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
