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

可视化图解算法47：包含min函数的栈

news 2025/6/7 20:29:57

1. 题目

牛客网面试笔试 TOP101 | LeetCode 155. 最小栈

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

数据范围：操作数量满足 0≤n≤300 ，输入的元素满足 ∣val∣≤10000 进阶：栈的各个操作的时间复杂度是 O(1) ，空间复杂度是 O(n)

示例:

输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出: -1,2,1,-1

解析:

"PSH-1"表示将-1压入栈中，栈中元素为-1

"PSH2"表示将2压入栈中，栈中元素为2，-1

“MIN”表示获取此时栈中最小元素==>返回-1

"TOP"表示获取栈顶元素==>返回2

"POP"表示弹出栈顶元素，弹出2，栈中元素为-1

"PSH1"表示将1压入栈中，栈中元素为1，-1

"TOP"表示获取栈顶元素==>返回1

“MIN”表示获取此时栈中最小元素==>返回-1

示例1

输入：

["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

返回值：

-1,2,1,-1

2. 解题思路

我们常用的栈的每次入栈、出栈的都是单个的数据，要实现包含min函数的栈，我们可以这样操作：每次入栈、出栈的数据为一对，这一对数据包括出入栈的数据、当前栈的最小值。

具体操作为：

定义一个栈，栈中存储的是二维数组（n*2：n行2列），第0列存储的是入栈的数据，第1列存储的是入栈中的最小值。
栈为空，直接入栈。
栈不为空，比较当前值与栈中的最小值，更新栈顶最小值（使得入栈的min值是最小的）。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372593
Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367849
Golang版本：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364847

3. 编码实现

核心代码如下：

// 定义一个栈，栈中存储的是二维数组（n*2：n行2列），第0列存储的是入栈的数据，第1列存储的是入栈中的最小值
var stack [][]intfunc init() {stack = make([][]int, 0)}
func Push(node int) {// write code here//1. 栈为空，直接入栈if len(stack) == 0 {stack = append([][]int{{node, node}}, stack...)return}//2. 栈不为空，比较当前值与栈中的最小值，更新栈顶最小值minVal := min(node, stack[0][1])stack = append([][]int{{node, minVal}}, stack...)
}func min(val1 int, val2 int) int {if val1 < val2 {return val1}return val2
}
func Pop() {// write code herestack = stack[1:]
}
func Top() int {// write code here//取出栈顶中的第0列return stack[0][0]
}
func Min() int {// write code here//取出栈顶中的第1列return stack[0][1]
}

具体完整代码你可以参考下面视频的详细讲解。

Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372593
Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367849
Golang版本：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364847

4.小结

我们常用的栈的每次入栈、出栈的都是单个的数据，要实现包含min函数的栈，我们可以这样操作：每次入栈、出栈的数据为一对，这一对数据包括出入栈的数据、当前栈的最小值。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807
Java编码实现：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss161443488
Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997