# 「力扣」第 155 题：最小栈（简单）
# 题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
pop、top和getMin操作总是在 非空栈 上调用。
# 思路分析
这道题的思想很简单：以空间换时间，使用辅助栈是常见的做法。
在代码实现的时候有两种方式：
- 辅助栈和数据栈同步
特点：编码简单，不用考虑一些边界情况，就有一点不好：辅助栈可能会存一些“不必要”的元素。
- 辅助栈和数据栈不同步
特点：由「辅助栈和数据栈同步」的思想，我们知道，当数据栈进来的数越来越大的时候，我们要在辅助栈顶放置和当前辅助栈顶一样的元素，这样做有点浪费。基于这一点，我们做一些「优化」，但是在编码上就要注意一些边界条件。
（1）辅助栈为空的时候，必须放入新进来的数；
（2）新来的数小于或者等于辅助栈栈顶元素的时候，才放入，特别注意这里“等于”要考虑进去，因为出栈的时候，连续的、相等的并且是最小值的元素要同步出栈；
（3）出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈。
总结一下：出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。
对比：个人觉得“同步栈”的方式更好一些，因为思路清楚，因为所有操作都同步进行，所以调试代码、定位问题也简单。“不同步栈”，虽然减少了一些空间，但是在“出栈”、“入栈”的时候还要做判断，也有性能上的消耗。
# 方法一：辅助栈和数据栈同步
参考代码 1：
Java 代码：
import java.util.Stack;
public class MinStack {
// 数据栈
private Stack<Integer> data;
// 辅助栈
private Stack<Integer> helper;
/**
* initialize your data structure here.
*/
public MinStack() {
data = new Stack<>();
helper = new Stack<>();
}
// 思路 1：数据栈和辅助栈在任何时候都同步
public void push(int x) {
// 数据栈和辅助栈一定会增加元素
data.add(x);
if (helper.isEmpty() || helper.peek() >= x) {
helper.add(x);
} else {
helper.add(helper.peek());
}
}
public void pop() {
// 两个栈都得 pop
if (!data.isEmpty()) {
helper.pop();
data.pop();
}
}
public int top() {
if(!data.isEmpty()){
return data.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
public int getMin() {
if(!helper.isEmpty()){
return helper.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
}
Python 代码：
class MinStack:
# 辅助栈和数据栈同步
# 思路简单不容易出错
def __init__(self):
# 数据栈
self.data = []
# 辅助栈
self.helper = []
def push(self, x):
self.data.append(x)
if len(self.helper) == 0 or x <= self.helper[-1]:
self.helper.append(x)
else:
self.helper.append(self.helper[-1])
def pop(self):
if self.data:
self.helper.pop()
return self.data.pop()
def top(self):
if self.data:
return self.data[-1]
def getMin(self):
if self.helper:
return self.helper[-1]
复杂度分析：
- 时间复杂度：
，“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大，都只是有限个步骤，因此时间复杂度是： ； - 空间复杂度：
，这里 是读出的数据的个数。
# 方法二：辅助栈和数据栈不同步
参考代码 2：
Java 代码：
import java.util.Stack;
public class MinStack {
// 数据栈
private Stack<Integer> data;
// 辅助栈
private Stack<Integer> helper;
/**
* initialize your data structure here.
*/
public MinStack() {
data = new Stack<>();
helper = new Stack<>();
}
// 思路 2：辅助栈和数据栈不同步
// 关键 1：辅助栈的元素空的时候，必须放入新进来的数
// 关键 2：新来的数小于或者等于辅助栈栈顶元素的时候，才放入（特别注意这里等于要考虑进去）
// 关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了
public void push(int x) {
// 辅助栈在必要的时候才增加
data.add(x);
// 关键 1 和 关键 2
if (helper.isEmpty() || helper.peek() >= x) {
helper.add(x);
}
}
public void pop() {
// 关键 3：data 一定得 pop()
if (!data.isEmpty()) {
// 注意：声明成 int 类型，这里完成了自动拆箱，从 Integer 转成了 int，因此下面的比较可以使用 "==" 运算符
// 参考资料：https://www.cnblogs.com/GuoYaxiang/p/6931264.html
// 如果把 top 变量声明成 Integer 类型，下面的比较就得使用 equals 方法
int top = data.pop();
if(top == helper.peek()){
helper.pop();
}
}
}
public int top() {
if(!data.isEmpty()){
return data.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
public int getMin() {
if(!helper.isEmpty()){
return helper.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
}
Python 代码：
class MinStack:
# 辅助栈和数据栈不同步
# 关键 1：辅助栈的元素空的时候，必须放入新进来的数
# 关键 2：新来的数小于或者等于辅助栈栈顶元素的时候，才放入（特别注意这里等于要考虑进去）
# 关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了
def __init__(self):
# 数据栈
self.data = []
# 辅助栈
self.helper = []
def push(self, x):
self.data.append(x)
# 关键 1 和关键 2
if len(self.helper) == 0 or x <= self.helper[-1]:
self.helper.append(x)
def pop(self):
# 关键 3：【注意】不论怎么样，数据栈都要 pop 出元素
top = self.data.pop()
if self.helper and top == self.helper[-1]:
self.helper.pop()
return top
def top(self):
if self.data:
return self.data[-1]
def getMin(self):
if self.helper:
return self.helper[-1]
复杂度分析：
- 时间复杂度：
，“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大，都只有有限个步骤，因此时间复杂度是： ； - 空间复杂度：
，这里 是读出的数据的个数。
作者：liweiwei1419 链接：https://suanfa8.com/stack/solutions-1/0155-min-stack 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。