[LeetCode][155]【学习日记】最小栈——记录每个时刻的最小值

2024-03-07 07:20

本文主要是介绍[LeetCode][155]【学习日记】最小栈——记录每个时刻的最小值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

最小栈

请你设计一个最小栈。它提供pushpoptop操作,并能在常数时间内检索到最小元素的栈。

实现MinStack类:

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

输入: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[2],[-3],[],[],[],[]]
输出: [null,null,null,null,-3,null,2,-2]
解释: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(2); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 2. minStack.getMin(); --> 返回 -2.

提示:

-231 <= val <= 231 - 1 pop、top 和 getMin 操作总是在 非空栈 上调用 push、pop、top 和 getMin 最多被调用 3 * 104 次

注意: 本题与主站 155 题相同:https://leetcode-cn.com/problems/min-stack/

解法1:使用 map 排序并统计

  • 利用 map 自动排序的特点,将栈元素值作为 key,压栈时对应的 key 的 value 自增,需要查询最小值的时候返回第一个元素即可
  • 出栈时,对应的 key 的 value 自减,为 0 时则删除这个键值对,表示栈中没有这个数值的元素
  • 这个解法的缺点是,保存了所有元素的计数值,但是其实有一些元素的计数值是不需要保存的,解法2 解决了这个问题
class MinStack {vector<int> vec;map<int,int> m;public:/** initialize your data structure here. */MinStack() {}void push(int x) {vec.push_back(x);if(m.find(x)==m.end()) m[x]=1;else m[x]++;}void pop() {int temp = vec.back();vec.pop_back();if(!(--m[temp])) m.erase(temp);}int top() {return *(vec.end()-1);}int getMin() {return (*m.begin()).first;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

解法2:只保留每个时刻栈中的最小元素

  • 由于出栈必须按照一定的顺序,所以只需要在入栈的时候保存每一次入栈后的最小值,就可以方便地在出栈的时候进行最小值的更新
    在这里插入图片描述
class MinStack {stack<int> s, minS;
public:/** initialize your data structure here. */MinStack() {}void push(int x) {s.push(x);if(minS.empty() || minS.top()>=x) minS.push(x);}void pop() {if(minS.top()==s.top()) minS.pop();s.pop();}int top() {return s.top();}int getMin() {return minS.top();}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

这篇关于[LeetCode][155]【学习日记】最小栈——记录每个时刻的最小值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/782762

相关文章

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者(Producer)配置1. 创建 Spr

k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)

《k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)》本文记录在K8s上运行的MySQL/MariaDB备份方案,通过工具容器执行mysqldump,结合定时任务实... 目录前言一、获取需要备份的数据库的信息二、备份步骤1.准备工作(X86)1.准备工作(arm)2.手

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项

Python UV安装、升级、卸载详细步骤记录

《PythonUV安装、升级、卸载详细步骤记录》:本文主要介绍PythonUV安装、升级、卸载的详细步骤,uv是Astral推出的下一代Python包与项目管理器,主打单一可执行文件、极致性能... 目录安装检查升级设置自动补全卸载UV 命令总结 官方文档详见:https://docs.astral.sh/

统一返回JsonResult踩坑的记录

《统一返回JsonResult踩坑的记录》:本文主要介绍统一返回JsonResult踩坑的记录,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录统一返回jsonResult踩坑定义了一个统一返回类在使用时,JsonResult没有get/set方法时响应总结统一返回

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

java对接海康摄像头的完整步骤记录

《java对接海康摄像头的完整步骤记录》在Java中调用海康威视摄像头通常需要使用海康威视提供的SDK,下面这篇文章主要给大家介绍了关于java对接海康摄像头的完整步骤,文中通过代码介绍的非常详细,需... 目录一、开发环境准备二、实现Java调用设备接口(一)加载动态链接库(二)结构体、接口重定义1.类型

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志,日志文件自动归档和压缩2.1、