155.最小栈
发布日期：2025-06-19 06:00:22
浏览次数：4
分类：精选文章
本文共 522 字，大约阅读时间需要 1 分钟。
设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈。以下是具体的解决方案：
链栈实现方案
为了实现上述功能，我们采用链栈（双向链表）结构，通过每个栈节点存储其值以及当前栈中最小值的一种巧妙方法。
结构定义
栈的每个节点包含以下信息：
data：当前节点的值。min_val：当前节点及其后继节点中的最小值。next：指向下一个节点的指针。
栈操作实现
push(x)：
- 创建一个新节点，
data字段为x，min_val字段为x。 - 如果栈为空，新节点成为栈顶，
min_val字段为x。 - 否则，新节点的
min_val字段为当前栈顶的min_val和x中的较小值。 - 新节点的
next指向当前栈顶节点。 - 更新栈顶指针和
min_val。
pop()：
- 检查栈是否为空，若为空，返回错误。
- 取得栈顶节点p。
- 栈顶更新为p的
next节点。 - 更新栈顶的
min_val为新的栈顶节点的min_val。
top()：
- 返回栈顶节点的
data值。
getMin()：
- 返回栈顶节点的
min_val值。
栈释放：
- 从栈顶节点开始，依次释放每个节点的内存，直到栈底。
这种设计使得所有操作的时间复杂度均为O(1)，包括快速检索栈中的最小值。
发表评论
最新留言
第一次来，支持一个
[***.219.124.196]2026年05月30日 00时01分57秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
php截取字符串，无乱码
2023-03-01
php手冊,php手冊之變量范圍
2023-03-01
PHP手机号码归属地查询API接口
2023-03-01
PHP执行耗时脚本实时输出内容
2023-03-01
PHP扩展安装
2023-03-01
PHP扩展数据库连接参数说明详解
2023-03-01
php把get参数放入数组_php怎么将数组转为url参数？
2023-03-01
PHP投票小程序
2023-03-01
php拆分数组不改变key值
2023-03-01
php接口返回数据 用echo 还是return?
2023-03-01
php接口返回状态,大家一般怎么规范接口返回内容
2023-03-01
php接收formdata上传的多个文件,使用formData（）上传多个文件
2023-03-01
PHP操作csv文件导入+导出
2023-03-01
php操作mysql用select_php如何操作mysql获取select 结果
2023-03-01
PHP操作符与控制结构
2023-03-01
PHP支付宝SDK使用,电脑网页支付
2023-03-01
php支付宝手机网页支付类实例
2023-03-01
PHP改变数组key值的方法
2023-03-01
php教程之php空白页的原因及解决方法
2023-03-01
PHP数据库操作
2023-03-01
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 475221117 位访客