【LeetCode 算法笔记】155. 最小栈
目录
- 问题描述
- 单个栈实现
- 双栈实现
- 不开辟额外空间
问题描述
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入:
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出:
[null,null,null,null,-3,null,0,-2]
解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
单个栈实现
题目只是要求 在常数时间内检索到最小元素 ,对其他操作没有要求,那么可以牺牲 pop() 操作的性能是一种可行的办法。
class MinStack:def __init__(self):self.stack = []self.min = float('inf')def push(self, val: int) -> None:self.stack.append(val)if self.min > val:self.min = valdef pop(self) -> None:s = self.stack.pop()if self.stack:if s == self.min:self.min = min(self.stack)else:self.min = float('inf')def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min
getMin() 方法的算法复杂度为: O ( 1 ) O(1) O(1)
如果做 n 次进栈出栈操作,算法总的复杂度为: O ( N 2 ) O(N^2) O(N2)
双栈实现
进一步来说,如果出栈的复杂度不想那么高的话,可以使用一点额外空间来换取速度。
具体来说,再维护一个最小栈,顶部存储当前栈中元素的最小值。
class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, val: int) -> None:if not self.stack or self.getMin() > val:self.min_stack.append(val)else:self.min_stack.append(self.getMin())self.stack.append(val)def pop(self) -> None:self.stack.pop()self.min_stack.pop()def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min_stack[-1]
getMin() 方法的算法复杂度为: O ( 1 ) O(1) O(1)
如果做 n 次进栈出栈操作,算法总的复杂度为: O ( N ) O(N) O(N)
不开辟额外空间
网上有人说他在面试的时候被要求,不额外开辟空间,下面列了我找到的答案。
相当于把 双栈实现 中的双栈合并为单个栈,于是栈里存储最小值和当前值之间的差值。每一次出栈的时候,通过这个插值还原出上一个时刻的最小值。
class MinStack:def __init__(self):"""initialize your data structure here."""self.stack = []self.min_value = -1def push(self, x: int) -> None:if not self.stack:self.stack.append(0)self.min_value = xelse:diff = x-self.min_valueself.stack.append(diff)self.min_value = self.min_value if diff > 0 else xdef pop(self) -> None:if self.stack:diff = self.stack.pop()if diff < 0:top = self.min_valueself.min_value = top - diffelse:top = self.min_value + diffreturn topdef top(self) -> int:return self.min_value if self.stack[-1] < 0 else self.stack[-1] + self.min_valuedef getMin(self) -> int:return self.min_value if self.stack else -1
getMin() 方法的算法复杂度为: O ( 1 ) O(1) O(1)
如果做 n 次进栈出栈操作,算法总的复杂度为: O ( N ) O(N) O(N)
相关文章:
【LeetCode 算法笔记】155. 最小栈
目录 问题描述单个栈实现双栈实现不开辟额外空间 问题描述 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop()…...
面试题 05.01. 插入
目录 一:题目: 二:代码: 三:结果: 一:题目: 给定两个整型数字 N 与 M,以及表示比特位置的 i 与 j(i < j,且从 0 位开始计算)。…...
稠密向量检索、稀疏向量检索、BM25检索三者对比
在当今的信息检索领域,随着人工智能和自然语言处理技术的发展,稠密向量检索和稀疏向量检索成为了两种主要的研究方向。稠密向量检索依托于高维空间中的向量表示,能够捕捉文档的深层语义信息,而稀疏向量检索则侧重于关键词的匹配&a…...
UEFI学习笔记(六):EDK II 模块:Libraries,DriversApplication
UEFI学习笔记(六):EDK II Modules:Libraries,Application&Drivers 一、模块(Modules)的概念1、Library模块2、Application模块3、Driver模块4、Application和Driver的区别 二、EDK II 实现U…...
详解 Pandas 的透视表函数
Pandas 的透视表函数主要为 pivot() 和 pivot_table(),主要的功能为对 DataFrame 的行和列进行重新组合来重塑数据。 一、pivot 函数 pivot 函数只能对数据进行重塑,不能进行聚合 1. 数据准备 import pandas as pddf1 pd.DataFrame({department_id: […...
基于python+django+vue的农业管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于pythondjangovueMySQL的农…...
动态内存管理之malloc,free,calloc和realloc函数
Hello,各位小伙伴们,小编在这里祝福各位中秋佳节快乐呀,今天让我们来学习一下动态内存管理吧! 引言 像我们之前在开辟一段空间的时候你可能会使用整型变量来申请一块空间,或者使用数组来申请一段连续的空间ÿ…...
Android 13 固定systemUI的状态栏为黑底白字,不能被系统应用或者三方应用修改
目录 一.背景 二.思路 三.代码流程 1.colos.xml自定义颜色 2.设置状态栏的背景颜色 3.对View进行操作 ①.对Clock(状态栏左侧的数字时钟)进行操作 ②.对电池(BatteryMeterView)进行操作 4.锁屏状态栏 5.patch汇总 一.背景 客户需求将状态栏固定成黑底白字,并且不能让系…...
【CTF Reverse】XCTF GFSJ1092 easyEZbaby_app Writeup(Android+逆向工程+Java)
easyEZbaby_app 究极简单的安卓逆向 解法 得到一个 apk 安装包。 用 jadx 打开,搜索文本 flag,加载所有。 flag 是 obj obj2,来自用户的用户名和密码。 Override // android.view.View.OnClickListenerpublic void onClick(View view) {St…...
ubuntu 22.04 ~24.04 如何修改登录背景
ubuntu 22.04 ~24.04 如何修改登录背景 背景:由于22.04 登录gdm的变更,之前的修改登录背景的方案已经无法使用。现在给大家分享新的使用方法: 1,下载如下路径的脚本: https://download.csdn.net/download/xdhyqd/89…...
Andrej Karpathy谈AI未来:自动驾驶、Transformer与人机融合
引言 在人工智能领域,Andrej Karpathy 是一个无法忽视的名字。从他早期在 OpenAI 的工作,到后来担任 Tesla 的 AI 主管,他在自动驾驶、深度学习等方面的贡献广为人知。最近,卡帕西做客了著名的播客节目 No Priors,他在…...
Vue使用query传参Boolean类型,刷新之后转换为String问题
做项目时发现第一次进入页面时传参是正常的Boolean类型,刷新之后变成了String,这是浏览器进行的一次强制转换; vue-router 传参,不管是 params 形式还是query形式传参,在页面刷新后,params 和 query 对象中…...
开源模型应用落地-qwen模型小试-调用Qwen2-VL-7B-Instruct-更清晰地看世界(一)
一、前言 学习Qwen2-VL ,为我们打开了一扇通往先进人工智能技术的大门。让我们能够深入了解当今最前沿的视觉语言模型的工作原理和强大能力。这不仅拓宽了我们的知识视野,更让我们站在科技发展的潮头,紧跟时代的步伐。 Qwen2-VL 具有卓越的图像和视频理解能力,以及多语言支…...
国学盛典 致敬先贤 《老子与道德经》纪录片研讨会在北京善品堂国学馆圆满落幕
9月10日,《老子与道德经》纪录片研讨会在北京善品堂国学馆圆满落幕。中国著名表演艺术家、曾饰演央视86版电视剧《西游记》中“孙悟空”的六小龄童先生与两百余人传统文化传播者、践行者、爱好者齐聚一堂,共同交流。本次会议由中国文化促进会福文化工作委…...
sqlgun新闻管理系统
一,打开主页 1.输入框测试回显点 -1union select 1,2,3# 出现回显点2 2.查看数据库表名 -1union select 1,database(),3# 3.查看表名 -1union select 1,2,group_concat(table_name) from information_schema.tables where table_schemasqlgunnews# 4.查看admin中…...
react hooks--useState
概述 useState 可以使函数组件像类组件一样拥有 state,也就说明函数组件可以通过 useState 改变 UI 视图。那么 useState 到底应该如何使用,底层又是怎么运作的呢,首先一起看一下 useState 。 问题:Hook 是什么? 一个 Hook 就是…...
C/C++:优选算法(持续更新~~)
一、双指针 1.1移动零 链接:283. 移动零 - 力扣(LeetCode) 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操…...
【qt信号槽-6】槽函数不执行的一种原因——未知线程
背景: 项目需要调用第三方库,又要涉及多线程,遇到了在connect成功之后,槽函数依然不执行的情况。按照常理,槽函数不执行无非就几种情况: 要么connect未成功。 要么disconnect,或者对象被销毁…...
Leetcode面试经典150题-162.寻找峰值
解法都在代码里,不懂就留言或者私信 想清楚的话会特别简单,你可能想不到这是个二分。。。 class Solution {/**本题题目规定我们只能用O(logN)的时间复杂度来解题,这显然就是让二分嘛而题目给的数组本身是无需,怎么二分呢其实我…...
Vue组件:模板引用ref属性的使用
Vue 组件系列文章: 《Vue组件:创建组件、注册组件、使用组件》 《Vue组件:使用Prop实现父组件向子组件传递数据》 《Vue组件:使用$emit()方法监听子组件事件》 《Vue组件:插槽》 《Vue组件:混入》 《Vue组件…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
