---
typora-copy-images-to: images\leetcode155最小栈
---
# Leetcode 155. 最小栈
题目:
```
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
## 辅助栈解法(1)-辅助栈与数据栈大小一致,入栈出栈同步
因为需要每次都能够取到栈中的最小值,肯定是不能全部出栈之后遍历再对比了,只能考虑其他的办法来获取最小值.
那就需要以空间换时间,新增一个辅助栈,数据栈每次入栈时的数据都与辅助栈的栈顶进行对比,如果小于栈顶,则在辅助栈压入当前数据,否则继续压入辅助栈中的最小值,此时辅助栈的栈顶永远都是最小值.
如图:
```java
//辅助栈与数据栈大小一致,入栈出栈同步
class MinStack {
Stack<Integer> data;
//声明一个辅助栈
Stack<Integer> helper;
/** initialize your data structure here. */
public MinStack() {
data = new Stack();
helper = new Stack();
}
public void push(int x) {
data.add(x);
//如果新加入的值比原来的最小值小的话,则压入X,否则继续压入原有最小值
if(helper.isEmpty() || helper.peek() >= x){
helper.add(x);
}else{
helper.add(helper.peek());
}
}
public void pop() {
//出栈需要一起出栈
if(!data.isEmpty()){
data.pop();
helper.pop();
}
}
public int top() {
//返回最上级值即可
return data.peek();
}
public int getMin() {
//返回辅助栈的最小值
return helper.peek();
}
}
```
### 复杂度
空间复杂度:O(N);
时间复杂度:O(1);
## 辅助栈解法(2)-辅助栈与数据栈大小不一致,入栈出栈不同步
新增一个辅助栈,每次只有新增的值**小于等于**当前辅助栈栈顶值才会push进入,需要注意的是pop的时候,如果数据栈出栈的值等于当前栈顶值时,则一起出栈,此时辅助栈中的栈顶值还是最小值.
如图:
```java
Stack<Integer> data;
//声明一个辅助栈
Stack<Integer> helper;
/** initialize your data structure here. */
public MinStack2() {
data = new Stack();
helper = new Stack();
}
public void push(int x) {
data.add(x);
//如果新加入的值比原来的最小值小的话,则压入X,否则继续压入原有最小值
if(helper.isEmpty() || helper.peek() >= x){
helper.add(x);
}
}
public void pop() {
if(!data.isEmpty()){
//如果数据栈值等于现在辅助栈最小值,则需要将辅助栈也出栈
if (data.peek().equals(helper.peek())) {
helper.pop();
}
data.pop();
}
}
public int top() {
//返回最上级值即可
return data.peek();
}
public int getMin() {
//返回辅助栈的最小值
return helper.peek();
}
```
### 复杂度
空间复杂度:O(n)
时间复杂度:O(1)
## 单栈解法-新增变量存储最小值
如果只能使用一个栈的话,我们想到了使用一个最小值来存储最小值,在持续入栈的情况下是没有问题的,例如入栈2,3,1,0 此时最小值为0,但是一旦我们将最小值出栈之后,将会导致倒数第二小的值丢失,此时最小值依旧是0,无法更新为1,那我们如果只有一个栈的话,只能将每次的最小值一起压入单栈.出栈的话就要考虑对比是否是最小值,如果是和min一样的最小值,则将出两个栈,并将min值更新为第二个出栈的值
如图:
```java
Stack<Integer> data;
//设置为最大值,以免影响判断
int minValue = Integer.MAX_VALUE;
/** initialize your data structure here. */
public MinStack3() {
data = new Stack();
}
public void push(int x) {
//相当于每次压栈的时候,如果有比之前的值更小的值的时候,将上次的最小值先压入,再压入真实data值
if (x <= minValue) {
data.add(minValue);
minValue = x;
}
data.add(x);
}
public void pop() {
if(!data.isEmpty()){
//因为前面多压了数值,如果出栈的值正好是当前最小值,则需要将倒数第二小的值一起出栈,并且将最小值更新
if (data.pop() == minValue) {
minValue = data.pop();
}
}
}
public int top() {
//返回最上级值即可
return data.peek();
}
public int getMin() {
//返回辅助栈的最小值
return minValue;
}
}
```
Leetcode 155. 最小栈