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

剑指 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个定时器 三种&#xff08;4&#xff09;STM32定时器区别 二、通用定时器特点 2.1 功能特点描述 STM3 F4的通…...

cmake 入门三 常用变量和指令

cmake常用变量 一、cmake 变量引用的方式&#xff1a; 前面我们已经提到了&#xff0c;使用${}进行变量的引用。在IF 等语句中&#xff0c;是直接使用变量名而不通过${}取值 二&#xff0c;cmake 自定义变量的方式&#xff1a; 主要有隐式定义和显式定义两种&#xff0c;一…...

Linux基础命令-find搜索文件位置

文章目录 find 命令介绍 语法格式 命令基本参数 参考实例 1&#xff09;在root/data目录下搜索*.txt的文件名 2&#xff09;搜索一天以内最后修改时间的文件&#xff1b;并将文件删除 3&#xff09;搜索777权限的文件 4&#xff09;搜索一天之前变动的文件复制到test…...

获取浏览器硬件资源的媒体数据(拍照、录音、录频、屏幕共享)

目录一、window.navigator 对象包含有关访问者浏览器的信息取二、MediaDevices1.使用麦克风2.使用摄像头&#xff08;和音频一样&#xff09;3.拍照4.录屏三、MediaRecorder(录制,可录制音频视屏)一、window.navigator 对象包含有关访问者浏览器的信息取 <!DOCTYPE html>…...

Java入门教程||Java 日期时间||Java 正则表达式

Java 日期时间java.util包提供了Date类来封装当前的日期和时间。Date类提供两个构造函数来实例化Date对象。第一个构造函数使用当前日期和时间来初始化对象。Date( )第二个构造函数接收一个参数&#xff0c;该参数是从1970年1月1日起的毫秒数。Date(long millisec)Date对象创建…...

详解八大排序算法

文章目录前言排序算法插入排序直接插入排序:希尔排序(缩小增量排序)选择排序直接选择排序堆排序交换排序冒泡排序快速排序hoare版本挖坑法前后指针版本快速排序的非递归快速排序总结归并排序归并排序的非递归实现&#xff1a;计数排序排序算法复杂度及稳定性分析总结前言 本篇…...

python库streamlit学习笔记

什么是streamlit&#xff1f; Streamlit是一个免费的开源框架&#xff0c;用于快速构建和共享漂亮的机器学习和数据科学Web应用程序。它是一个基于Python的库&#xff0c;专为机器学习工程师设计。数据科学家或机器学习工程师不是网络开发人员&#xff0c;他们对花几周时间学习…...

C/C++开发,无可避免的内存管理(篇一)-约束好跳脱的内存

一、养成内存管理好习惯 1.1 养成动态对象创建、调用及释放好习惯 开发者手动接管内存分配时&#xff0c;必须处理这两个任务。分配原始内存时&#xff0c;必须在该内存中构造对象&#xff1b;在释放该内存之前&#xff0c;必须保证适当地撤销这些对象。如果你的项目是c项目&am…...

在React项目中引入字体文件并使用

一、背景 设计稿里某些文字所用的字体&#xff0c;系统默认不支持。 比如设计需要的这个字体&#xff1a;EmerlandRegular&#xff0c;即使在css里将文字字体设置为他们&#xff0c;实际效果也显示不出来。 二、现象及原因 1、样式 2、期待效果 3、实际效果 实际上是因为这个…...

STM32 CubeMX按键点灯

本文代码使用 HAL 库。 文章目录前言一、按键原理图二、CubeMX 创建工程三、代码讲解&#xff1a;1. GPIO的输入HAL库函数&#xff1a;2. 消抖&#xff1a;3. 详细代码四&#xff0c;实验现象&#xff1a;总结前言 我们继续讲解 stm32 f103&#xff0c;这篇文章将详细 为大家讲…...

2023链动2+1模式到底是什么?带你了解核心规则

2023链动21模式到底是什么&#xff1f;带你了解核心规则 2023-02-24 梦龙 大家好&#xff0c;我是你们熟悉而又陌生的好朋友梦龙&#xff0c;一个创业期的年轻人 传统的直销模式产品低价高卖&#xff0c;消费者难以接受。虽然直销省去了传统流通渠道的中间环节&#xff0c;但…...

【Java面试八股文宝典之基础篇】备战2023 查缺补漏 你越早准备 越早成功!!!——Day14

大家好&#xff0c;我是陶然同学&#xff0c;软件工程大三今年实习。认识我的朋友们知道&#xff0c;我是科班出身&#xff0c;学的还行&#xff0c;但是对面试掌握不够&#xff0c;所以我将用这100多天更新Java面试题&#x1f643;&#x1f643;。 不敢苟同&#xff0c;相信大…...

K8S篇-搭建kubenetes集群

安装环境 这里使用pve虚拟机搭建三台centos机器&#xff0c;搭建过程参考: Centos篇-Centos Minimal安装 此次安装硬件配置 CPU&#xff1a;2C 内存&#xff1a;2G 存储&#xff1a;64G 环境说明 操作系统&#xff1a;Centos 7.9 内核版本&#xff1a;6.2.0-1.el7.elrepo…...

文本生成图像简述4——扩散模型、自回归模型、生成对抗网络的对比调研

基于近年来图像处理和语言理解方面的技术突破&#xff0c;融合图像和文本处理的多模态任务获得了广泛的关注并取得了显著成功。 文本生成图像&#xff08;text-to-image&#xff09;是图像和文本处理的多模态任务的一项子任务&#xff0c;其根据给定文本生成符合描述的真实图像…...

财务共享建设,为什么需要电子影像系统?

某集团作为投资性集团公司&#xff0c;业务遍布全国20多个省市&#xff0c;控股公司200余家&#xff0c;业务范围涉及火电、供热、风电、天然气天然气、水务、铁路、港口、酒店、地产等20多个细分行业。 伴随着集团企业的快速发展&#xff0c;某集团在管理中面临“点多、面广、…...

「RISC-V Arch」SBI 规范解读(下)

第六章 定时器扩展&#xff08;EID #0x54494D45"TIME"&#xff09; 这个定时器扩展取代了遗留定时器扩展&#xff08;EID #0x00&#xff09;&#xff0c;并遵循 v0.2 中定义的调用规约。 6.1 函数&#xff1a;设置定时器&#xff08;FID #0&#xff09; struct sbi…...

Android framework socketpair

简述 在Linux中&#xff0c;socketpair函数可以用于创建一对相互连接的、通信域为AF_UNIX的套接字&#xff0c;其中一个套接字可用于读取&#xff0c;另一个套接字可用于写入。可以使用这对套接字在同一进程内进行进程间通信&#xff08;IPC&#xff09;。 以下是使用socketp…...

腾讯在海外游戏和短视频广告领域的新增长机会

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 腾讯(00700)的收入在过去几个季度一直在下降&#xff0c;部分原因是由于新冠疫情导致的经济放缓以及中国监管机构对大型科技公司的监管收紧导致游戏行业萎缩造成的。 然而&#xff0c;猛兽财经认为&#xff0c;这些不利因素…...

查找该学号学生的成绩。

从键盘输入某班学生某门课的成绩&#xff08;每班人数最多不超过40人&#xff09;&#xff0c;当输入为负值时&#xff0c;表示输入结束&#xff0c;试编程从键盘任意输入一个学号&#xff0c;查找该学号学生的成绩。**输入格式要求&#xff1a;"%ld"(学号) "%l…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...