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

LeetCode_Hot100_栈_155最小栈_Python

题目

设计一个支持 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.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

自己的一些思考

我每次在看到这个题目的时候都会写一点思考,有些时候思考不一定全都对,很多时候都是一个暴力思考。但是思考的流程可能比较重要。有错误也请大家斧正,不过最后的代码一定会是修改且通过用例的。

栈是一个LIFO结构,后进先出。有三种基本的操作。1.PUSH,即把一个元素压入栈顶,push和append的效果都是一样的。可是push用在栈里面,append常见于列表。2.pop,即为去除栈顶上的元素,3.Top/peek,返回栈顶的元素

这个代码想要实现的就是写一个栈,这个栈能够有基础的操作,且能够返回最小值

class MinStack:def __init__(self):def push(self, val: int) -> None:def pop(self) -> None:def top(self) -> int:def getMin(self) -> int:# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

题目给的参考例子是这个,我们就拿这个来试着分析一下。

 def __init__(self):

    def push(self, val: int) -> None:

先初始化这个栈,可以写成self.stack=[],这个self指向调用的当前对象,指向对象自身的引用,能够初始化这个对象,然后这里使用的是self.stack=[],创建一个空栈

    def push(self, val: int) -> None:

这里在栈顶添加一个元素可以使用这个代码,self.stack.push(val)

    def pop(self) -> None:

这里返回最上面的这个也可以用stack里面的方法,self.stack.pop()

    def top(self) -> int:

这里要获取top,return self.stack[-1][0],最后面一个元素(可能是一个列表,返回这个列表的第一个值)

   def getMin(self) -> int:

那么我到这里的时候就会有一点迷惑,这个Min该怎么样去处理呢,于是我去看了一下题解。

题解

题解当中提到使用一个叫做“辅助栈”的概念

而且这个题解在栈中间插入了元组(里面有不同数据类型的一种数据结构,可以存储一组有序的元素)

什么是辅助栈,辅助栈最经典的例子就是这个最小栈,就是保存栈内所有元素的最小值。有新添加进来的元素都能够获取到这个的最小值,当新元素来的时候,如果它比辅助栈的栈顶元素更小,就把这个新的元素压入辅助栈,当元素出栈是,如果它和辅助栈的栈顶元素大小一致时,就把辅助栈栈顶也给弹出(POP)

class MinStack(object):def __init__(self):"""initialize your data structure here.、初始化栈"""self.stack = []def push(self, x):""":type x: int:rtype: void"""#栈内每一个元素都是一个二元组(tuple),#(x)(x)前一个(x)是真实的元素,后面一个(x)是最小#如果不是空值,就把自身和现在栈顶的二元组的1做一个比较,#哪个小,新栈顶上面的[1]就是这个元素if not self.stack:self.stack.append((x, x))else:self.stack.append((x, min(x, self.stack[-1][1])))def pop(self):""":rtype: void"""self.stack.pop()def top(self):""":rtype: int"""return self.stack[-1][0]def getMin(self):""":rtype: int"""return self.stack[-1][1]# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

TODO

1.第一刷:2024/3/10

2.切记辅助栈这个概念,可以通过元组这种方法来实现

相关文章:

LeetCode_Hot100_栈_155最小栈_Python

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

力扣每日一题 找出数组的第 K 大和 小根堆 逆向思维(TODO:二分+暴搜)

Problem: 2386. 找出数组的第 K 大和 文章目录 思路复杂度&#x1f496; 小根堆&#x1f496; TODO&#xff1a;二分 暴搜 思路 &#x1f468;‍&#x1f3eb; 灵神题解 复杂度 时间复杂度: 添加时间复杂度, 示例&#xff1a; O ( n ) O(n) O(n) 空间复杂度: 添加空间复杂…...

Git的介绍

导出项目依赖 # 以后项目给别人需要导出项目依赖&#xff0c;放在项目路径下&#xff0c;以后在运行项目前&#xff0c;先安装依赖 一般约定俗成都叫 requirements.txt,但是会有别的&#xff1a;req.txt | dev.txt # 两种方式&#xff1a; 1、虚拟环境所有装的第三方&…...

websocket+心跳

1.直接上代码 let ws //websocket实例 let lockReconnect false //避免重复连接 let wsUrl //初始化websocket getWebSocketurl() async function getWebSocketurl() {try {// const data await getInfo()sid.value localStorage.getItem(Refresh-Token)wsUrl ws://192.…...

人工智能在信息系统安全中的运用

一、 概述 对于企业和消费者来讲&#xff0c;人工智能是非常有用的工具&#xff0c;那又该如何使用人工智能技术来保护敏感信息?通过快速处理数据并预测分析&#xff0c;AI可以完成从自动化系统到保护信息的所有工作。尽管有些黑客利用技术手段来达到自己的目的&#xff0c;但…...

[python3] 装饰器

装饰器是Python中一种特殊的语法&#xff0c;用于在不修改原函数代码的情况下&#xff0c;为函数添加额外的功能。 装饰器基于函数闭包和函数作为第一类对象的特性实现。 原理&#xff1a; Python中的装饰器本质上是一个函数或类&#xff0c;它接受一个函数作为参数&#xff0…...

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:Checkbox)

提供多选框组件&#xff0c;通常用于某选项的打开或关闭。 说明&#xff1a; API version 11开始&#xff0c;Checkbox默认样式由圆角方形变为圆形。 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口…...

【三十】springboot项目上高并发解决示例

互相交流入口地址 整体目录&#xff1a; 【一】springboot整合swagger 【二】springboot整合自定义swagger 【三】springboot整合token 【四】springboot整合mybatis-plus 【五】springboot整合mybatis-plus 【六】springboot整合redis 【七】springboot整合AOP实现日志操作 【…...

原生JavaScript,根据后端返回JSON动态【动态列头、动态数据】生成表格数据

前期准备&#xff1a; JQ下载地址&#xff1a; https://jquery.com/ <!DOCTYPE html> <html><head><meta charset"utf-8"><title>JSON动态生成表格数据,动态列头拼接</title><style>table {width: 800px;text-align: cen…...

OD_2024_C卷_200分_9、园区参观路径【JAVA】【动态规划】

package odjava;import java.util.Scanner;public class 九_园区参观路径 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(); // 长 -> 行数int m sc.nextInt(); // 宽 -> 列数int[][] matrix new int[n][m]; // 地图…...

校园小情书微信小程序源码 | 社区小程序前后端开源 | 校园表白墙交友小程序

项目描述&#xff1a; 校园小情书微信小程序源码 | 社区小程序前后端开源 | 校园表白墙交友小程序 功能介绍&#xff1a; 表白墙 卖舍友 步数旅行 步数排行榜 情侣脸 漫画脸 个人主页 私信 站内消息 今日话题 评论点赞收藏 服务器环境要求&#xff1a;PHP7.0 MySQL5.7 效果…...

数据结构小记【Python/C++版】——散列表篇

一&#xff0c;基础概念 散列表&#xff0c;英文名是hash table&#xff0c;又叫哈希表。 散列表通常使用顺序表来存储集合元素&#xff0c;集合元素以一种很分散的分布方式存储在顺序表中。 散列表是一个键值对(key-item)的组合&#xff0c;由键(key)和元素值(item)组成。键…...

前端框架的发展史可以追溯到早期的静态网页时代

前端框架的发展史可以追溯到早期的静态网页时代。以下是前端框架的主要发展阶段&#xff1a; 静态网页时代&#xff1a;在互联网的初期&#xff0c;网页主要由HTML、CSS和JavaScript构成。这些网页是静态的&#xff0c;没有复杂的交互和动态内容。 原生JavaScript时代&#xf…...

迷宫可行路径数

题目描述 现有一个n∗m大小的迷宫&#xff0c;其中1表示不可通过的墙壁&#xff0c;0表示平地。每次移动只能向上下左右移动一格&#xff08;不允许移动到曾经经过的位置&#xff09;&#xff0c;且只能移动到平地上。求从迷宫左上角到右下角的所有可行路径的条数。 输入描述…...

消息队列学习

消息队列是什么 消息队列&#xff1a;Kafka、RocketMQ、RabbitMQ等 腾讯云CMQ消息队列介绍是这么说的&#xff1a; 腾讯云消息队列&#xff08;Cloud Message Queue&#xff0c;以下简称 CMQ&#xff09;是分布式的消息队列服务&#xff0c;用于存储进程间传输的消息&#xff…...

API接口技术开发店铺详情接口采集店铺ID、卖家ID、掌柜名字、店铺名、店铺类型、店铺主页、店铺等级、店铺评分、联系方式等数据接入演示

API接口技术开发店铺详情接口采集店铺ID、卖家ID、掌柜名字、店铺名、店铺类型、店铺主页、店铺等级、店铺评分、联系方式等数据&#xff0c;可以按照以下步骤进行接入演示&#xff1a; 注册并获取API密钥&#xff1a; 在电商平台的开发者中心注册账号。创建一个应用&#xff0…...

ffmpeg maxrate 导致转码输出的内容包含随机性

https://trac.ffmpeg.org/wiki/Limiting%20the%20output%20bitrate 问题 领导提出了一个问题&#xff0c;为什么转码后的视频大小字节数据都不一样&#xff0c;这问到我了&#xff0c;一时语塞。查一下吧&#xff0c;没有什么资料支撑。主动试一下。 尝试 首先尝试一下直接…...

Graphpad Prism10.2.1(395) 安装教程 (含Win/Mac版)

GraphPad Prism GraphPad Prism是一款非常专业强大的科研医学生物数据处理绘图软件&#xff0c;它可以将科学图形、综合曲线拟合&#xff08;非线性回归&#xff09;、可理解的统计数据、数据组织结合在一起&#xff0c;除了最基本的数据统计分析外&#xff0c;还能自动生成统…...

Cocos Creator 2d光照

godot游戏引擎是有2d光照的&#xff0c;用起来感觉还是很强大的&#xff0c;不知道他是怎么搞的&#xff0c;有时间看看他们怎么实现的。 之前一直以为cocos社区里面没有2d光照的实现&#xff0c;偶然看到2d实现的具体逻辑&#xff0c;现在整理如下&#xff0c; 一&#xff1…...

5款好用的AI办公软件,一键轻松制作PPT、视频,提升工作效率!

众所周知&#xff0c;AI 人工智能技术已渗透到生活的方方面面&#xff0c;无论是很多人早已用上的智能音箱、语音助手&#xff0c;还是新近诞生的各种 AI 软件工具&#xff0c;背后都离不开 AI 人工智能技术的加持。 对于各类新生的 AI 软件工具&#xff0c;人们很容易「选边站…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...