【LeetCode 热题 100】155. 最小栈
Problem: 155. 最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度:O(1)
- 空间复杂度:O(N)
整体思路
这段代码旨在实现一个经典的特殊数据结构:最小栈 (Min Stack)。这个数据结构除了支持常规栈的 push
、pop
和 top
操作外,还必须支持一个 getMin
操作,该操作能够以 常数时间 O(1) 返回栈中当前的最小元素。
该算法的核心思想是,不只在栈中存储元素值本身,而是 将每个元素与其“当时”的栈内最小值绑定在一起存储。
-
数据结构选择:
- 算法选择了一个双端队列
Deque<int[]>
并将其用作栈。 - 关键在于,栈中存储的不是单个整数,而是一个大小为 2 的整型数组
int[]
。这个数组被设计成一个元组(pair):{value, current_minimum}
。pair[0]
存储的是被push
进栈的实际值val
。pair[1]
存储的是当这个val
被压入时,栈内所有元素(包括val
)的最小值。
- 算法选择了一个双端队列
-
核心操作逻辑:
push(val)
: 当一个新值val
被推入栈时,算法会创建一个新的元组。新元组的第二部分(current_minimum
)通过比较val
和 上一个状态的最小值(即当前栈顶元组的第二部分getMin()
)来确定。这样,每个层级的栈都“知道”自己及以下所有元素的最小值。getMin()
: 由于每个状态都保存了到它为止的最小值,获取整个栈的最小值就变得非常简单:只需查看当前栈顶元组的第二部分st.peek()[1]
即可。这是一个 O(1) 操作。top()
: 获取栈顶元素的值,同样只需查看当前栈顶元组的第一部分st.peek()[0]
。pop()
: 弹出栈顶元组。这个操作非常巧妙,因为当一个元组被弹出后,新暴露出的栈顶元组中保存的最小值,就自动地变回了上一个状态的最小值,无需任何额外计算。
-
初始化处理:
- 构造函数中
st.push(new int[]{0, Integer.MAX_VALUE});
的操作是一个哨兵节点(Sentinel Node)。它的目的是简化push
操作的逻辑。通过预置一个最小值为Integer.MAX_VALUE
的节点,第一次调用push
时,Math.min(getMin(), val)
就能自然地得到val
作为第一个真正的最小值,从而避免了在push
方法中写if (st.isEmpty())
的特殊判断。
- 构造函数中
完整代码
/*** 一个支持在常数时间内检索到最小元素的栈。*/
class MinStack {// 使用 Deque 作为栈的底层实现。// 存储的是一个大小为2的数组,格式为 {value, current_minimum}。private final Deque<int[]> st = new ArrayDeque<>();/*** 构造函数,初始化最小栈。*/public MinStack() {// 推入一个哨兵节点或初始节点。// Integer.MAX_VALUE 确保第一个被推入的真实元素的最小值就是它自身。// 这样可以避免在 push 方法中对空栈进行特殊处理。st.push(new int[]{0, Integer.MAX_VALUE});}/*** 将元素 val 推入栈中。* @param val 要推入的元素值*/public void push(int val) {// 创建一个新的元组 {val, min(当前最小值, val)}。// getMin() 会返回上一个状态的最小值。// 将新值与上一个状态的最小值比较,得到新的当前最小值。st.push(new int[]{val, Math.min(getMin(), val)});}/*** 删除栈顶的元素。*/public void pop() {// 直接弹出栈顶的元组 {value, current_minimum}。// 栈的状态(包括最小值)会自动恢复到上一个状态。st.pop();}/*** 获取栈顶元素。* @return 栈顶元素的值*/public int top() {// 栈顶元组的第一个元素 [0] 存储的是实际值。return st.peek()[0];}/*** 在常数时间内检索到栈中的最小元素。* @return 栈中的最小元素值*/public int getMin() {// 栈顶元组的第二个元素 [1] 存储的是到当前状态为止的最小值。return st.peek()[1];}
}
时空复杂度
时间复杂度:O(1)
push(val)
: 该操作包括getMin()
(即peek
)、Math.min
和st.push()
。对于ArrayDeque
,这些都是 O(1) 的均摊时间复杂度。pop()
:st.pop()
是 O(1) 的均摊时间复杂度。top()
:st.peek()
是 O(1) 的时间复杂度。getMin()
:st.peek()
是 O(1) 的时间复杂度。
综合分析:
该数据结构的所有公开操作(push
, pop
, top
, getMin
)都具有 O(1) 的时间复杂度,满足了设计要求。
空间复杂度:O(N)
- 主要存储开销:空间复杂度由栈
st
的大小决定。 - 空间大小:对于用户推入的每一个元素,我们都在栈中存储一个包含两个整数的数组
int[]
。如果栈中有N
个元素(不包括哨兵节点),那么实际存储了N
个int[2]
对象。 - 综合分析:
所需的额外空间与栈中元素的数量N
成线性关系。因此,空间复杂度为 O(N)。
参考灵神