【LeetCode热题100】--155.最小栈
155.最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素

思路:
根据栈的先进先出的特性,对于栈来说,如果一个元素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> 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 ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元…...
Allegro 17.2如何直接更新元件封装?
想必很多从事电子设计的小伙伴,都有这样的经历:有些时候原理图和PCB设计是由不同的工程师负责,然后偶尔需要在没有原理图的情况下直接对PCB作品进行操作,如更新元件封装等操作,这种环节不仅费时费力,效率贼…...
高效数据管理:Java助力实现Excel数据验证
摘要:本文由葡萄城技术团队原创并首发。转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。 前言 在Java中,开发者可以使用一些开源的库(如Apache POI)…...
Easysearch Chart 0.2.0都有哪些变化
Easysearch Chart 包更新了,让我们来看看都有哪些变化: Docker 镜像升级 Service 名称调整,支持 NodePort 模式部署 现在让我们用 NodePort 模式部署一下: # 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爬虫提高排名
在如今竞争激烈的互联网时代,网站的SEO优化变得尤为重要。而Python爬虫作为一种强大的工具,可以帮助网站主们提升搜索排名,吸引更多的流量和用户。本文将为您揭秘如何利用Python爬虫来改善您的SEO优化,并帮助您提升搜索排名。无论…...
SQL获取正数第N个或倒数第N个数据
这里我们使用Order By与Limit的组合: Order By:可以将某个序列值按照从大到小或从小到大排序Limit:如果类似Limit 5表示前5个,Limit 3,5表示从第4个位置(以0为开始)开始往后取5个 通过这样的组合就可以实…...
链表(2)——带头双向循环链表
🍁一、链表的分类 🌕1.单向或者双向 🌕2.带头或者不带头(有无哨兵) 🌕3.循环或者不循环 🌕4.无头单向非循环链表(常用) 🌕5.带头双向循环链表(常用…...
C语言 函数指针
函数指针是C语言中的一种特殊类型,它允许你像操作变量一样操作函数。函数指针的主要用途是存储并后续调用一组函数。 在C语言中,函数指针的定义通常如下所示: 返回类型 (*指针变量名)(参数类型) 例如,如果你有一个返回整数并接受…...
F. Vasilije Loves Number Theory
Problem - F - Codeforces 思路:分析一下题意,对于第一种操作来说,每次乘以x,那么nn*x,然后问是否存在一个a使得gcd(n,a)1并且n*a的约数个数等于n,有最大公约数等于1我们能够知道其实这两个数是互质的&…...
electron打包后主进程下载文件崩溃
electronvue3写了一个小项目,实现了一个文件下载功能 存在的问题 打包后,应用下载文件崩溃代码 // 渲染进程window.electron.ipcRenderer.invoke(save-file, {path: r.filePath,fileurl: previewUrl,}).then(response > {console.log(response ----…...
Spring实例化源码解析之Custom Events下集(九)
上集从官网的角度讲解了基本的使用和源码的内容,没有深入的进行分析,本章将从源码的角度分析ApplicationEvent、ApplicationListener、ApplicationEventMulticaster这三者之间的关系。 initApplicationEventMulticaster 上一章后续部分给出了源码的含义…...
python numpy库关键函数说明
python numpy库函数说明 np.argwhere()np.dtype()np.shape()np.zeros() np.argwhere() 输入参数是一个基本的逻辑表达式,输出检索结果的索引值。 >>> 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如何执行一个程序 一、程序存储空间 本节说的空间主要是指内存空间,即程序如何分…...
IP协议总结
一、定义。 IP全称为Internet Protocol,是TCP/IP协议族中的一员,负责实现数据在网络上的传输。它是一种无连接、不可靠的数据报协议。 IP协议常用于Internet网络和局域网中,它通过将数据包进行分组并进行逐跳转发来实现数据在网络中的传输。…...
微信支付v2
文档: https://pay.weixin.qq.com/wiki/doc/api/index.html 微信小程序:https://pay.weixin.qq.com/wiki/doc/api/jsapi.php?chapter11_1 需要一个微信认证后的小程序,,还需要一个,在微信商户平台,&…...
tcpdump(二)命令行参数讲解(一)
一 tcpdump实战详解 1、我们做抓包,一般都需要指定条件,保证对系统的CPU、内存、磁盘资源不会产生过大的响应备注: 遇到过tcpdump持续抓包导致系统挂了2、条件: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内存…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
