(栈)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.提示-231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次# 思路思路首先理解题目意思有两个目的实现栈功能可以通过getMin获取到 栈 中的 最小值辅助栈在这里这个最小值的获取便使用栈去承载这个最小值使用minStack表示实际元素的存储的栈使用stack表示栈先进后出只要stack中有有元素出栈则对应的这个最小值minstack栈也要出栈其出栈后minstack栈内的第一个元素还是stack栈里面的最小值示例如下// 初始值 stacknull minStackINT_MAX // -2入栈 stack-2 minStackINT_MAX-2 // 0入栈 stack-20 minStackINT_MAX-2-2 // -3入栈 stack-20-3 minStackINT_MAX-2-2-3Deque中用于栈操作入栈、出栈、查看栈顶的核心方法说明入栈push(E e)将元素压入栈顶即添加到Deque的头部遵循 LIFO 原则出栈pop()移除并返回栈顶元素即Deque的头部元素遵循 LIFO 原则查看栈顶元素不移除peek()获取栈顶元素即Deque的头部元素但不移除该元素单向链表使用Node去存储这个过程每个节点对应栈里的一个元素同时携带了当前栈的最小值信息key存入栈的元素本身的值供top()方法返回栈顶元素value从栈底到当前节点为止栈内的最小值供getMin()方法直接返回next指向下一个节点栈中更靠下、更早入栈的元素整个栈用单链表的头部作为栈顶入栈 链表头插法新节点插在最前面出栈 链表头删法直接把头指针后移一位所有操作都是 O (1) 时间classNode{intkey;intvalue;Nodenext;publicNode(intkey,intvalue){this.keykey;this.valuevalue;this.nextnull;};publicNode(intkey,intvalue,Nodenode){this.keykey;this.valuevalue;// 反向this.nextnode;}}注意入栈时更新的是当前这整个链表即nodenewNode而非node.nextnewNode出栈时nodenode.next;// 初始值 innull nodenull // -2入栈 stack-2 node{-2,-2} // 0入栈 stack-20 node{0,-2}{-2,-2} // -3入栈 stack-20-3 node{-3,-3}{0,-2}{-2,-2} // getMin() // pop() stack-20 node{0,-2}{-2,-2}算法辅助栈classMinStack{DequeIntegerstack;DequeIntegerminStack;publicMinStack(){stacknewLinkedList();minStacknewLinkedList();minStack.push(Integer.MAX_VALUE);}publicvoidpush(intval){stack.push(val);minStack.push(Math.min(minStack.peek(),val));}publicvoidpop(){stack.pop();minStack.pop();}publicinttop(){returnstack.peek();}publicintgetMin(){returnminStack.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(); */单向链表classMinStack{Nodenode;publicMinStack(){}publicvoidpush(intval){if(nodenull){nodenewNode(val,val);}else{intminMath.min(node.value,val);NodenewNodenewNode(val,min,node);nodenewNode;}}publicvoidpop(){nodenode.next;}publicinttop(){returnnode.key;}publicintgetMin(){returnnode.value;}classNode{intkey;intvalue;Nodenext;publicNode(intkey,intvalue){this.keykey;this.valuevalue;this.nextnull;};publicNode(intkey,intvalue,Nodenode){this.keykey;this.valuevalue;this.nextnode;}}}/** * 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(); */

相关新闻

C语言数组传参机制解析与最佳实践

C语言数组传参机制解析与最佳实践

1. 数组传参的本质与常见误区在C语言中,数组作为函数参数传递是一个看似简单却暗藏玄机的操作。新手程序员常常困惑于为什么数组在函数内部无法直接获取其长度,这源于C语言中数组传参的特殊机制——数组名在作为参数传递时会退化为指针。这种退化机制意味…

2026/11/15 6:01:32 阅读更多 →
Agent Governance Toolkit版本迁移指南:从v4到v5的平滑过渡

Agent Governance Toolkit版本迁移指南:从v4到v5的平滑过渡

Agent Governance Toolkit版本迁移指南:从v4到v5的平滑过渡 【免费下载链接】agent-governance-toolkit AI Agent Governance Toolkit — Policy enforcement, zero-trust identity, execution sandboxing, and reliability engineering for autonomous AI agents. …

2026/11/18 18:29:57 阅读更多 →
专业级Windows系统组件清理架构深度解析:3大模块实现彻底卸载

专业级Windows系统组件清理架构深度解析:3大模块实现彻底卸载

专业级Windows系统组件清理架构深度解析:3大模块实现彻底卸载 【免费下载链接】Remove-MS-Edge Uninstall Microsoft Edge with an executable or batch script. 项目地址: https://gitcode.com/gh_mirrors/re/Remove-MS-Edge Remove-MS-Edge项目为Windows系…

2026/11/16 23:28:04 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻