华为 OD 训练营 · 题解精讲
LeetCode155、最小栈
LeetCode155、最小栈 预习和复习可以查看我的讲解视频。
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
题目解析
由于需要在常数时间内找到最小的元素，那么说明肯定是不能使用遍历，因为遍历是 O(n) 级别的时间复杂度，那么只能使用辅助空间进行存储，这是一种空间换时间的思想。 这里我们设置两个栈：普通栈和辅助栈。 push 操作 普通栈：直接添加 push 进来的值 辅助栈：每次 push 一个新元素的时候，将普通栈中最小的元素 push 进辅助栈中 pop 操作 普通栈：直接移除普通栈中的栈顶元素 辅助栈：判断普通栈中刚刚移除的栈顶元素值是否和此时辅助栈中的栈顶元素相同，如果是则将辅助栈中的栈顶元素移除，否则不执行操作，这样的目的是为了让辅助栈中的栈顶元素始终是普通栈中的最小值。 top 操作 普通栈：返回普通栈的栈顶元素 辅助栈：不执行操作 getMin 操作 普通栈：不执行操作 辅助栈：返回辅助栈的栈顶元素
参考代码
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 最小栈（ LeetCode 155 ）:https://leetcode-cn.com/problems/min-stack/
class MinStack:
def __init__(self):
# 首先定义好两个栈
# 一个栈叫做 stack，负责栈的正常操作
self.stack = []
# 一个栈叫做 min_stack，负责获取 stack 中的最小值，它等价于遍历 stack 中的所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈
self.min_stack = []
def push(self, x: int) -> None:
# 新添加的元素添加到 stack 中
self.stack.append(x)
# 判断 min_stack 是否为空，如果为空，直接同时把新添加的元素添加到 minStack 中
# 如果 min_stack 不为空
if self.min_stack:
# 获取 min_stack 的栈顶元素
top = self.min_stack[-1]
# 只有新添加的元素不大于 top 才允许添加到 minStack 中，目的是为了让 minStack 从栈底到栈顶是降序的
if x <= top :
self.min_stack.append(x)
# min_stack 中没有元素，所以直接把新添加的元素添加到 min_stack 中
else:
self.min_stack.append(x)
def pop(self) -> None:
# 让 stack 执行正常的 pop 操作就行
pop = self.stack[-1]
self.stack.pop()
# 由于 minStack 中的所有元素都是来自于 stack 中，所以 stack 删除元素后，minStack 也要考虑是否需要删除元素
# 否则的话，minStack 有可能保存一个 stack 中不存在的元素
# 首先，获取 minStack 的栈顶元素
top = self.min_stack[-1]
# 再判断 top 这个栈顶元素是否和 stack 移除的元素相等，如果相等，那么需要把 minStack 中的栈顶元素一并移除
if pop == top:
# 移除 min_stack 的栈顶元素
self.min_stack.pop()
def top(self) -> int:
# 返回 stack 的栈顶元素
return self.stack[-1]
def getMin(self) -> int:
# 返回 min_stack 的栈顶元素
return self.min_stack[-1]
四、复杂度分析
时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。