【算法】栈算法——最小栈

题解:最小栈(栈算法)

目录

  • 1.题目
  • 2.题解
  • 3.总结

1.题目

题目链接:LINK
在这里插入图片描述

这个题目题意说的有点绕,说白了让你在常数时间内检索到最小元素就是O(1)时间复杂度下找到栈中最小的元素。

2.题解

思路:这个栈可以内嵌套两个库栈来进行解决,一个库栈负责正常入数据,另一个库栈负责在O(1)时间复杂度下找出(记录)栈最小值。

class MinStack 
{
private:stack<int> _normalst;stack<int> _minst;public:MinStack() {}void push(int val) {_normalst.push(val);if(_minst.empty() || _minst.top() >= val){_minst.push(val);}}void pop() {if(_minst.top() == _normalst.top()){_minst.pop();}_normalst.pop();}int top() {return _normalst.top();}int getMin() {return _minst.top();}
};/*** 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();*/

思考:用一个库栈 + 一个变量可以解决这个题目吗?为什么?
答:不能。
因为如果用一个变量去存储最小值,如果栈的最小值被pop掉了,变量很难去更新到次小值。
但是把一个变量去替换为一个栈就不会有这个问题了,因为可以把之前出现的“最小值”都记录下来。

图解如下:
在这里插入图片描述
在这里插入图片描述

3.总结

思路是关键点。
关键点:最小栈的实现: 两个栈 or 栈+变量???


EOF

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/330395.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

商品发布功能

文章目录 1.SPU和SKU介绍1.SPU2.SKU3.两者之间的关系 2.完成商品发布界面1.组件引入1.commoditylaunch.vue 引入到 src/views/modules/commodity下2.multiUpload.vue 引入到 src/components/upload/multiUpload.vue 2.创建菜单1.创建目录2.创建菜单&#xff0c;注意菜单路由要匹…

开源博客项目Blog .NET Core源码学习(25:App.Hosting项目结构分析-13)

本文学习并分析App.Hosting项目中后台管理页面的文章管理页面。   文章管理页面用于显示、检索、新建、编辑、删除文章数据&#xff0c;以便在前台页面的首页、文章专栏、文章详情页面显示文章数据。文章管理页面附带一新建及编辑页面&#xff0c;以支撑新建和编辑文章数据。…

交换机部分综合实验

实验要求 1.内网IP地址使用172.16.0.0/16 2.sw1和sW2之间互为备份; 3.VRRP/mstp/vlan/eth-trunk均使用; 4.所有pc均通过DHcP获取Ip地址; 5.ISP只配置IP地址; 6.所有电脑可以正常访问IsP路由器环回 实验拓扑 实验思路 1.给交换机创建vlan&#xff0c;并将接口划入vlan 2.在SW1和…

传输层 --- UDP

一、简述与回顾 传输层&#xff1a;负责数据能够从发送端传输接收端 在TCP/IP协议中&#xff0c;我们用"源IP"&#xff0c;"源端口号"&#xff0c;"目的IP"&#xff0c;"目的端口号"&#xff0c;和"协议号"来表示一个通信。…

Android studio关闭自动更新

Windows下&#xff1a; 左上角file - setting - Appearance & Behavier - system setting - update - 取消勾选

golang通过go-aci适配神通数据库

1. go-aci简介 go-aci是神通数据库基于ACI(兼容Oracle的OCI)开发的go语言开发接口&#xff0c;因此运行时需要依赖ACI驱动和ACI库的头文件。支持各种数据类型的读写、支持参数绑定、支持游标范围等操作。 2. Linux部署步骤 2.1. Go安装&#xff1a; 版本&#xff1a;1.9以上…

Spring Cache基本使用

Spring 从 3.1 版本开始定义缓存抽象来统一不同的缓存技术&#xff1b;在应用层面与后端存储之间&#xff0c;提供了一层抽象&#xff0c;这层抽象目的在于封装各种可插拔的后端存储( ehcache, redis, guava)&#xff0c;最小化因为缓存给现有业务代码带来的侵入。 一、Spring…

机器学习实验 --- 逻辑回归

第1关:逻辑回归核心思想 任务描述 本关任务:根据本节课所学知识完成本关所设置的编程题 #encoding=utf8 import numpy as npdef sigmoid(t):完成sigmoid函数计算:param t: 负无穷到正无穷的实数:return: 转换后的概率值:可以考虑使用np.exp()函数#********** Begin *******…

C语言-atoi()库函数的模拟实现

文章目录 前言一、atoi()库函数的介绍及使用1.1 atoi()库函数介绍1.2 atoi()库函数使用 二、atoi()库函数的模拟实现2.1 函数设计2.2 函数实现思路2.3 具体实现2.4 测试 总结 前言 本篇文章介绍c语言中库函数atoi()的使用&#xff0c;以及模拟实现库函数。 一、atoi()库函数的…

景源畅信电商:抖店需要的成本高吗?

在数字化时代的浪潮中&#xff0c;短视频平台迅速崛起&#xff0c;成为连接用户与商家的新桥梁。抖音作为其中的佼佼者&#xff0c;不仅改变了人们的娱乐方式&#xff0c;也催生了新型的电商模式——抖店。许多人好奇&#xff0c;入驻这样一个充满活力的平台&#xff0c;需要承…

【数据结构】第七节:堆

个人主页&#xff1a; 深情秋刀鱼-CSDN博客 数据结构专栏&#xff1a;数据结构与算法 源码获取&#xff1a;数据结构: 上传我写的关于数据结构的代码 (gitee.com) ​ 目录 一、堆 1.堆的概念 2.堆的定义 二、堆的实现 1.初始化和销毁 2.插入 向上调整算法 3.删除 向下调整算法…

DDoS攻击的最新动态及市场趋势分析

随着数字化转型的加速和网络连接设备的增加&#xff0c;分布式拒绝服务(Distributed Denial of Service, DDoS)攻击已经成为全球网络安全领域的一大威胁。根据最新的市场研究报告&#xff0c;预计到2028年&#xff0c;DDoS防护软件市场的复合年增长率将达到14%以上&#xff0c;…

Threes 特效 炫酷传送门HTML5动画特效

基于Three.js的HTML5 3D动画&#xff0c;这个动画模拟了游戏中的一个炫酷的3D场景&#xff0c;支持360度视角查看&#xff0c;也支持鼠标滚轮进行缩放。画面中主要展现了一个游戏中传送门的效果&#xff0c;同时还有路两边的围栏、灯笼、石头&#xff0c;以及星光闪闪的萤火虫&…

springboot vue 开源 会员收银系统 (2) 搭建基础框架

前言 完整版演示 前面我们对会员系统https://blog.csdn.net/qq_35238367/article/details/126174288进行了分析 确定了技术选型 和基本的模块 下面我们将从 springboot脚手架开发一套收银系统 使用脚手架的好处 不用编写基础的rabc权限系统将工作量回归业务本身生成代码 便于…

宿舍管理系统--毕业设计

毕业设计&#x1f4bc;MD5加密&#x1f512;SSM框架&#x1f3a8;Layui框架&#x1f384; 实现功能 管理员的登录与登出 管理员,班级,学生,宿舍&#xff0c;卫生&#xff0c;访客各模块增删改查 个别模块关联查询 各个模块数据导出Excel 一些截图

双向链表C++,C#,Java版,这些程序大多已经过测试,一直在用。

先C版吧&#xff0c;我最先用的是C#,后来是Java&#xff0c;后来改用C版的&#xff0c;因为现在一直在用C&#xff0c;单链 表一直没写上去&#xff0c;因为我很少用&#xff0c;用的是双链表。 执行代码例子1&#xff1a; int main() { _DList<_string> s…

重学java 40.多线程 — 死锁和线程状态

—— 24.5. 一、死锁 1.死锁介绍&#xff08;锁嵌套就有可能产生死锁&#xff09; 指的是两个或者两个以上的线程在执行的过程中由于竞争同步锁而产生的一种阻塞现象;如果没有外力的作用,他们将无法继续执行下去,这种情况称之为死锁 例&#xff1a; 两线程处于互相等待的状态&a…

nss刷题(3)

1、[SWPUCTF 2021 新生赛]include 根据提示传入一个file后显示了关于flag的代码 这是一个文件包含&#xff0c;考虑php伪协议&#xff0c;构造payload&#xff1a; ?filephp://filter/readconvert.base64-encode/resourceflag.php 2、[SWPUCTF 2021 新生赛]Do_you_know_http …

MyBatisPlus使用流程

引入依赖 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.4</version> </dependency> 版本号根据需要选取 在实体类上加注解声明&#xff0c;表信息 根据数…

go-zero 实战(5)

引入Prometheus 用 Prometheus 监控应用 1. 用 docker 启动 Prometheus 编辑配置位置&#xff0c;我将 prometheus.yaml 和 targets.json 文件放在了 /opt/prometheus/conf目录下 prometheus.yaml global:scrape_interval: 15s # 抓取间隔evaluation_interval: 15s # 评估…