- 本题核心是 实现得到栈中最小值的方法
双辅助栈
思路
-
一个栈保存正常的入栈出栈的元素，另一个栈去存最小值，即该栈的栈顶 保存当前栈中所有元素的最小值。
-
具体步骤
-
将第一个元素入栈。
-
新加入的元素如果大于栈顶元素，那么新加入的元素就不处理。
-
新加入的元素如果小于等于栈顶元素，那么就将新元素入栈。
-
出栈元素不等于栈顶元素，不操作。
-
出栈元素等于栈顶元素，那么就将栈顶元素出栈。
-
-
实例
入栈 3
| | | |
| | | |
|_3_| |_3_|
stack minStack
入栈 5 ， 5 大于 minStack 栈顶，不处理
| | | |
| 5 | | |
|_3_| |_3_|
stack minStack
入栈 2 ，此时右边的 minStack 栈顶就保存了当前最小值 2
| 2 | | |
| 5 | | 2 |
|_3_| |_3_|
stack minStack
出栈 2，此时右边的 minStack 栈顶就保存了当前最小值 3
| | | |
| 5 | | |
|_3_| |_3_|
stack minStack
出栈 5，右边 minStack 不处理
| | | |
| | | |
|_3_| |_3_|
stack minStack
出栈 3
| | | |
| | | |
|_ _| |_ _|
stack minStack
代码
/*
* 6ms
*/
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (!minStack.isEmpty()) {
int top = minStack.peek();
//小于的时候才入栈
if (x <= top) {
minStack.push(x);
}
}else{
minStack.push(x);
}
}
public void pop() {
int pop = stack.pop();
int top = minStack.peek();
//等于的时候再出栈
if (pop == top) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
单辅助栈 单变量存储min
- 相对于双辅助栈 ，使用变量min存储最小值 (分析思路很妙)
- 实例
入栈 3
| | min = 3
| |
|_3_|
stack
入栈 5
| | min = 3
| 5 |
|_3_|
stack
入栈 2
| 2 | min = 2?
| 5 |
|_3_|
stack
如果只用一个变量就会遇到一个问题，如果把 min 更新为 2，那么之前的最小值 3 就丢失了。
怎么把 3 保存起来呢？把它在 2 之前压入栈中即可。
入栈 2 ，同时将之前的 min 值 3 入栈，再把 2 入栈，同时更新 min = 2
| 2 | min = 2
| 3 |
| 5 |
|_3_|
stack
入栈 6
| 6 | min = 2
| 2 |
| 3 |
| 5 |
|_3_|
stack
出栈 6
| 2 | min = 2
| 3 |
| 5 |
|_3_|
stack
出栈 2
| 2 | min = 2
| 3 |
| 5 |
|_3_|
stack
上边的最后一个状态，当出栈元素是最小元素我们该如何处理呢？
我们只需要把 2 出栈，然后再出栈一次，把 3 赋值给 min 即可。
出栈 2
| | min = 3
| 5 |
|_3_|
stack
代码
/*
* 6ms
*/
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
//当前值更小
if(x <= min){
//将之前的最小值保存
stack.push(min);
//更新最小值
min=x;
}
stack.push(x);
}
public void pop() {
//如果弹出的值是最小值，那么将下一个元素更新为最小值
if(stack.pop() == min) {
min=stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
链表实现（最直观）
思路
- 每添加一个节点，更新min值 且每次在链表头部加入节点
代码
/*
* 5ms
*/
class MinStack {
class Node{
int value;
int min;
Node next;
Node(int x, int min){
this.value=x;
this.min=min;
next = null;
}
}
Node head;
//每次加入的节点放到头部
public void push(int x) {
if(null==head){
head = new Node(x,x);
}else{
//当前值和之前头结点的最小值较小的做为当前的 min
Node n = new Node(x, Math.min(x,head.min));
n.next=head;
head=n;
}
}
public void pop() {
if(head!=null)
head =head.next;
}
public int top() {
if(head!=null)
return head.value;
return -1;
}
public int getMin() {
if(null!=head)
return head.min;
return -1;
}
}