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

【LeetCode热题100】--155.最小栈

155.最小栈

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素

image-20231009101448266

思路:

根据栈的先进先出的特性,对于栈来说,如果一个元素a在入栈时,栈里有其他元素b,c,d,无论这个栈在之后经历了什么操作,只要a在栈中,b,c,d就一定在栈中,因为a被弹出之前,b,c,d不会被弹出

因此,在操作过程中的任意一个时刻,只要栈顶的元素是a,那么我们就可以确定栈里面现在的元素一定是a,b,c,d

可以在每个元素a入栈时把当前栈的最小值m存储起来,在这之后无论何时,如果栈顶元素是a,就可以直接返回存储的最小值m

算法:

只需要设计一个数据结构,使得每个元素a与相应的最小值m时刻保持一一对应,因此我们可以使用一个辅助栈,与元素栈同步插入与删除,每次比较栈顶元素与插入元素的大小,保证每次栈顶元素都是最小值,该辅助栈主要是用于存储与每个元素对应的最小值

  • 当一个元素要入栈时,取当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中
  • 当一个元素要出栈时,把辅助栈的栈顶元素也一并弹出
  • 在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中

image-20231009102554548

class MinStack {Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {xStack = new LinkedList<Integer>();minStack = new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(minStack.peek(),val));  //取当前辅助栈的栈顶存储的最小值}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}/*** 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();*/

相关文章:

【LeetCode热题100】--155.最小栈

155.最小栈 设计一个支持 push &#xff0c;pop &#xff0c;top 操作&#xff0c;并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元…...

Allegro 17.2如何直接更新元件封装?

想必很多从事电子设计的小伙伴&#xff0c;都有这样的经历&#xff1a;有些时候原理图和PCB设计是由不同的工程师负责&#xff0c;然后偶尔需要在没有原理图的情况下直接对PCB作品进行操作&#xff0c;如更新元件封装等操作&#xff0c;这种环节不仅费时费力&#xff0c;效率贼…...

高效数据管理:Java助力实现Excel数据验证

摘要&#xff1a;本文由葡萄城技术团队原创并首发。转载请注明出处&#xff1a;葡萄城官网&#xff0c;葡萄城为开发者提供专业的开发工具、解决方案和服务&#xff0c;赋能开发者。 前言 在Java中&#xff0c;开发者可以使用一些开源的库&#xff08;如Apache POI&#xff09…...

Easysearch Chart 0.2.0都有哪些变化

Easysearch Chart 包更新了&#xff0c;让我们来看看都有哪些变化&#xff1a; Docker 镜像升级 Service 名称调整&#xff0c;支持 NodePort 模式部署 现在让我们用 NodePort 模式部署一下&#xff1a; # helm search repo infinilabs NAME CHART VERSION …...

RV1126-RV1109-进入uboot的按键和名字显示-HOSTNAME

今天添加一个小功能,就是uboot是按CTRLC进入的 今日我做了一个定制,让按L或者l让也进入uboot指令模式,并且修改主板名字显示 默认是CTRLC:键码值是0x03(ASCII对照表) 于是代码中跟踪: //rv1126_rv1109/u-boot/common/console.c int ctrlc(void) { #ifndef CONFIG_SANDBOXif (…...

学习vue-router

可参见: vue-router 详解_vue router_七月J的博客-CSDN博客 https://www.cnblogs.com/chen-ao666/p/17144552.html vue-router的使用 使用vue-router的步骤: 创建路由组件 配置路由映射: 组件和路径映射关系 使用路由: 通过和 <router-link>: 该标签是一个vue-router中…...

Python爬虫提高排名

在如今竞争激烈的互联网时代&#xff0c;网站的SEO优化变得尤为重要。而Python爬虫作为一种强大的工具&#xff0c;可以帮助网站主们提升搜索排名&#xff0c;吸引更多的流量和用户。本文将为您揭秘如何利用Python爬虫来改善您的SEO优化&#xff0c;并帮助您提升搜索排名。无论…...

SQL获取正数第N个或倒数第N个数据

这里我们使用Order By与Limit的组合&#xff1a; Order By&#xff1a;可以将某个序列值按照从大到小或从小到大排序Limit&#xff1a;如果类似Limit 5表示前5个&#xff0c;Limit 3,5表示从第4个位置&#xff08;以0为开始&#xff09;开始往后取5个 通过这样的组合就可以实…...

链表(2)——带头双向循环链表

&#x1f341;一、链表的分类 &#x1f315;1.单向或者双向 &#x1f315;2.带头或者不带头&#xff08;有无哨兵&#xff09; &#x1f315;3.循环或者不循环 &#x1f315;4.无头单向非循环链表&#xff08;常用&#xff09; &#x1f315;5.带头双向循环链表&#xff08;常用…...

C语言 函数指针

函数指针是C语言中的一种特殊类型&#xff0c;它允许你像操作变量一样操作函数。函数指针的主要用途是存储并后续调用一组函数。 在C语言中&#xff0c;函数指针的定义通常如下所示&#xff1a; 返回类型 (*指针变量名)(参数类型) 例如&#xff0c;如果你有一个返回整数并接受…...

F. Vasilije Loves Number Theory

Problem - F - Codeforces 思路&#xff1a;分析一下题意&#xff0c;对于第一种操作来说&#xff0c;每次乘以x&#xff0c;那么nn*x&#xff0c;然后问是否存在一个a使得gcd(n,a)1并且n*a的约数个数等于n&#xff0c;有最大公约数等于1我们能够知道其实这两个数是互质的&…...

electron打包后主进程下载文件崩溃

electronvue3写了一个小项目&#xff0c;实现了一个文件下载功能 存在的问题 打包后&#xff0c;应用下载文件崩溃代码 // 渲染进程window.electron.ipcRenderer.invoke(save-file, {path: r.filePath,fileurl: previewUrl,}).then(response > {console.log(response ----…...

Spring实例化源码解析之Custom Events下集(九)

上集从官网的角度讲解了基本的使用和源码的内容&#xff0c;没有深入的进行分析&#xff0c;本章将从源码的角度分析ApplicationEvent、ApplicationListener、ApplicationEventMulticaster这三者之间的关系。 initApplicationEventMulticaster 上一章后续部分给出了源码的含义…...

python numpy库关键函数说明

python numpy库函数说明 np.argwhere()np.dtype()np.shape()np.zeros() np.argwhere() 输入参数是一个基本的逻辑表达式&#xff0c;输出检索结果的索引值。 >>> x np.arange(6).reshape(2,3) >>> x array([[0, 1, 2],[3, 4, 5]]) >>> np.argwhe…...

【Linux C】Linux如何执行一个程序(程序存储空间、系统调用、内核调用)

文章目录 一、程序存储空间1.1 C语言程序存储空间1.2 用户空间和内核空间1.3 用户模式和内核模式 二、内核调用-系统调用-C语言库函数2.1 系统调用和内核调用2.2 C语言库函数 三、Linux如何执行一个程序 一、程序存储空间 本节说的空间主要是指内存空间&#xff0c;即程序如何分…...

IP协议总结

一、定义。 IP全称为Internet Protocol&#xff0c;是TCP/IP协议族中的一员&#xff0c;负责实现数据在网络上的传输。它是一种无连接、不可靠的数据报协议。 IP协议常用于Internet网络和局域网中&#xff0c;它通过将数据包进行分组并进行逐跳转发来实现数据在网络中的传输。…...

微信支付v2

文档&#xff1a; https://pay.weixin.qq.com/wiki/doc/api/index.html 微信小程序&#xff1a;https://pay.weixin.qq.com/wiki/doc/api/jsapi.php?chapter11_1 需要一个微信认证后的小程序&#xff0c;&#xff0c;还需要一个&#xff0c;在微信商户平台&#xff0c;&…...

tcpdump(二)命令行参数讲解(一)

一 tcpdump实战详解 1、我们做抓包,一般都需要指定条件,保证对系统的CPU、内存、磁盘资源不会产生过大的响应备注&#xff1a; 遇到过tcpdump持续抓包导致系统挂了2、条件&#xff1a;1) tcpdump的 基础命令选项参数2) 真正的 过滤条件 抓包工具tcpdump用法说明 ① 参数学…...

10_8C++

X-Mind #include <iostream>using namespace std; class Rect { private:int width;int heigjt; public:void init(int w,int h){width w;heigjt h;}void set_w(int w){width w;}void set_h(int h){heigjt h;}void show(){cout << "矩形的周长" <…...

JVM篇---第七篇

系列文章目录 文章目录 系列文章目录一、Minor GC与Full GC分别在什么时候发生?二、你知道哪些JVM性能调优参数?(简单版回答)三、对象一定分配在堆中吗?有没有了解逃逸分析技术?一、Minor GC与Full GC分别在什么时候发生? 新生代内存不够用时候发生MGC也叫YGC,JVM内存…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

Electron简介(附电子书学习资料)

一、什么是Electron&#xff1f; Electron 是一个由 GitHub 开发的 开源框架&#xff0c;允许开发者使用 Web技术&#xff08;HTML、CSS、JavaScript&#xff09; 构建跨平台的桌面应用程序&#xff08;Windows、macOS、Linux&#xff09;。它将 Chromium浏览器内核 和 Node.j…...

Qt学习及使用_第1部分_认识Qt---Qt开发基本流程

前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...

简单聊下阿里云DNS劫持事件

阿里云域名被DNS劫持事件 事件总结 根据ICANN规则&#xff0c;域名注册商&#xff08;Verisign&#xff09;认定aliyuncs.com域名下的部分网站被用于非法活动&#xff08;如传播恶意软件&#xff09;&#xff1b;顶级域名DNS服务器将aliyuncs.com域名的DNS记录统一解析到shado…...