剑指 Offer 30. 包含min函数的栈
大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 30.包含min函数的栈。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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 次
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
如果只使用一个栈来实现 min 函数会发现 push() 和 pop() 操作可以达到 O(1) 的时间复杂度，但由于获取最小值需要遍历整个栈，所以 min 的操作的时间复杂度是 O(N) 级别，不满足要求。
压缩时间的一个方法是增加额外的空间，即再使用一个辅助栈。
- 数据栈：存储所有元素，
push()、pop()、top()操作都使用数据栈来完成 - 辅助栈：在辅助栈中，每次压入的元素只能比辅助栈的栈顶元素更小或者相等，如果更大，则重复再压入辅助栈的栈顶元素。
push() 函数
pop()函数
数据栈和辅助栈同时执行 pop() 操作。
top()函数
直接返回数据栈的栈顶元素。
min() 函数
直接返回辅助栈的栈顶元素。
2、规律
需要维护好辅助栈的元素，每次压入元素时都需要和辅助栈的栈顶元素对比，这样才能确保辅助栈的栈顶元素永远是最小的，执行 min() 函数是才可以做到 O(1) 的时间里获取到最小的元素。
3、匹配
栈。
4、边界
注意辅助栈为空的情况。
三、动画描述
隐藏内容
四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class MinStack {
// 构建两个栈
// stack1 代表数据栈
// stack2 代表辅助栈
Stack<Integer> stack1,stack2;
public MinStack() {
// 初始化
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
// 数据栈直接压入 x
stack1.add(x);
// 如果辅助栈是空，也直接压入 x
if(stack2.empty()){
stack2.add(x);
}else{
// 如果辅助栈的栈顶元素不小于 x，也直接压入 x
if(stack2.peek() >= x){
stack2.add(x);
}else{
//如果辅助栈的栈顶元素小于 x,则压入辅助栈原来的栈顶元素
stack2.add(stack2.peek());
}
}
}
public void pop() {
// 数据栈直接 pop
stack1.pop();
// 辅助栈直接 pop
stack2.pop();
}
public int top() {
// 返回数据栈的栈顶元素
return stack1.peek();
}
public int min() {
// 返回辅助栈的栈顶元素
return stack2.peek();
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(1)。
空间复杂度
空间复杂度为 O(N)。
七、相关标签
- 栈
