剑指 Offer 30. 包含min函数的栈
一、题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数，在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示：
- 1、各函数的调用总次数不超过 20000 次
二、解析思路
由于需要在常数时间内找到最小的元素，那么说明肯定是不能使用遍历，因为遍历是 O(n) 级别的时间，那么只能使用辅助空间进行存储，这是一种空间换时间的思想。
这里我们设置两个栈：普通栈和辅助栈。
1、push 操作
普通栈：直接添加 push 进来的值
辅助栈：每次 push 一个新元素的时候，将普通栈中最小的元素 push 进辅助栈中
2、pop 操作
普通栈：直接移除普通栈中的栈顶元素
辅助栈：判断普通栈中刚刚移除的栈顶元素值是否和此时辅助栈中的栈顶元素相同，如果是则将辅助栈中的栈顶元素移除，否则不执行操作，这样的目的是为了让辅助栈中的栈顶元素始终是普通栈中的最小值。
3、top 操作
普通栈：返回普通栈的栈顶元素
辅助栈：不执行操作
4、getMin 操作
普通栈：不执行操作
辅助栈：返回辅助栈的栈顶元素
三、参考代码
1、Java 版本参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// Java 中的 Stack 类设计有问题，大部分情况下是使用 LinkedList 来构建栈，但为了结合动画更好的理解这道题目，所以依旧使用 Stack
class MinStack {
// 创建两个栈
// 创建栈 stack1 ，用来作为数据栈
Stack<Integer> stack1;
// 创建栈 stack2 ，用来作为辅助栈
// stack2 存储 stack1 中所有【非严格降序】的元素
// 这意味着 stack2 中的【栈顶元素】是 stack1 中的【最小元素】，维护好 stack2 和 stack1 的这种关系
// 那么 min() 函数只需返回 stack2 的栈顶元素即可，并且时间复杂度为 O(1)
Stack<Integer> stack2;
// 这个函数是最小栈的初始化操作
// 由于题目要求我们用两个栈实现最小栈，所以在这个函数中初始化的是两个栈
public MinStack() {
// 初始化 stack1
stack1 = new Stack<Integer>();
// 初始化 stack2
stack2 = new Stack<Integer>();
}
// 这个函数是最小栈的压入操作
public void push(int x) {
// 数据栈 stack1 直接压入 x
stack1.push(x);
// 如果辅助栈 stack2 是空，可以直接压入 x
// 此时，由于只有一个元素，stack2 中的【栈顶元素】是 stack1 中的【最小元素】
if(stack2.empty()){
// stack2 直接压入 x
stack2.push(x);
// 如果辅助栈 stack2 不为空
// 那么考虑是否把 x 压入到辅助栈 stack2 中，目的是为了维护 stack2 和 stack1 的关系，让 stack2 中的【栈顶元素】是 stack1 中的【最小元素】
}else{
// 如果辅助栈 stack2 的栈顶元素大于或者等于 x ，那么可以把 x 压入到 stack2 中
// 这样做，stack2 中的【栈顶元素】还是 stack1 中的【最小元素】
if(stack2.peek() >= x){
// 可以把 x 压入到 stack2 中
stack2.push(x);
// 如果辅助栈 stack2 的栈顶元素小于 x ，那么就不能把 x 压入到 stack2 中了
}else{
// 为了让 stack1 和 stack2 的元素个数相同，动画更美观
// 这里执行一个操作，压入辅助栈【原来的栈顶元素】
stack2.push(stack2.peek());
}
}
}
// 这个函数是最小栈的弹出操作
// 栈的特征是先进后出
public void pop() {
// 数据栈 stack1 直接 pop
stack1.pop();
// 辅助栈 stack2 直接 pop
stack2.pop();
}
// 这个函数是获取最小栈的栈顶元素操作
// 栈的特征是先进后出
public int top() {
// 返回数据栈 stack1 的栈顶元素
return stack1.peek();
}
// 这个函数是获取最小栈的最小元素操作
public int min() {
// 由于 stack2 中的【栈顶元素】是 stack1 中的【最小元素】
// 所以，返回 stack2 的栈顶元素就是全部元素的最小值
return stack2.peek();
}
}
2、C++ 版本参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最小栈（ LeetCode 155 ）:https://leetcode-cn.com/problems/min-stack/
class MinStack {
public:
// 首先定义好两个栈
// 一个栈叫做 stk
stack<int> stk;
// 一个栈叫做 minstk，负责获取 stk 中的最小值，它等价于遍历 stk 中的所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈
stack<int> minstk;
MinStack() {
}
void push(int x) {
// 新添加的元素添加到 stk 中
stk.push(x);
// 判断 minstk 是否为空，如果为空，直接同时把新添加的元素添加到 minstk 中
// 如果 minstk 不为空
if (!minstk.empty()) {
// 获取 minstk 的栈顶元素
int top = minstk.top();
// 只有新添加的元素不大于 top 才允许添加到 minstk 中，目的是为了让 minstk 从栈底到栈顶是降序的
if (x <= top) {
// 此时，新添加的元素 x 小于 top，加入到 minstk 后依旧是从栈底到栈顶是降序的
minstk.push(x);
}
}else{
// 此时，minstk 中没有元素，所以直接把新添加的元素添加到 minstk 中
minstk.push(x);
}
}
void pop() {
// 让 stk 执行正常的 pop 操作就行
int pop = stk.top();
stk.pop();
// 由于 minstk 中的所有元素都是来自于 stk 中，所以 stk 删除元素后，minstk 也要考虑是否需要删除元素
// 否则的话，minstk 有可能保存一个 stk 中不存在的元素
// 首先，获取 minstk 的栈顶元素
int top = minstk.top();
// 再判断 top 这个栈顶元素是否和 stk 移除的元素相等，如果相等，那么需要把 minstk 中的栈顶元素一并移除
if (pop == top) {
// 移除 minstk 的栈顶元素
minstk.pop();
}
}
int top() {
// 返回 stk 的栈顶元素
return stk.top();
}
int getMin() {
// 返回 minstk 的栈顶元素
return minstk.top();
}
};
3、Python 版本参考代码
# 登录 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]
