题目：155. 最小栈
如果您已经有思路了，或者是N刷了，可以先自己写一遍。
题目分析
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈称为“最小栈”。
实现最小栈的关键在于如何在常数时间内获得最小值，同时保持栈的基本操作不变。
这通常需要使用额外的数据结构来辅助存储每个元素入栈时的当前最小值。
解题思路
主要由一下两种解题思路：
- 双栈法：使用两个栈，一个用来按顺序存储所有入栈元素（
stack），另一个用来存储每次入栈操作后的当前最小值（minStack）。这样，minStack的栈顶元素始终是stack中所有元素的最小值。
- 单栈+变量法：只使用一个栈来存储所有入栈元素，同时使用一个变量来记录当前的最小值。每次新元素入栈时，如果新元素比当前最小值还小，先将旧的最小值入栈，然后更新最小值变量并将新元素入栈。这样做可以保证最小值的正确更新和恢复。
初次刷题的朋友，建议先试用双栈法实现，因为它的逻辑更直观且容易实现。虽然装逼很重要，但是万一装逼失败就要被人笑话了。
接下来我们采用双栈法来实现最小栈。
双栈法
下面是使用Java语言的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| import java.util.Stack;
class MinStack {
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() || x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
if (stack.pop().equals(minStack.peek())) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
|
使用双栈法实现最小栈的关键在于如何同步维护所有元素的栈（stack）和每个状态下最小元素的栈（minStack），以确保getMin操作可以在常数时间内完成。
通过辅助栈优雅地解决了常数时间内检索最小元素的要求。
单栈+变量法
不过，有能力装逼，还是要尽量装逼一下的，如果是我，我会用单栈来实现，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| import java.util.Stack;
class MinStack {
private Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(new int[]{x, x});
} else {
int currentMin = stack.peek()[1];
stack.push(new int[]{x, Math.min(x, currentMin)});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
|
栈stack存储了元素值和该元素入栈时的最小值的配对（使用数组int[]表示）。每次push操作时，都会计算当前的最小值，这样即使最小元素被弹出，栈顶的第二个元素依然保留了入栈时的最小值信息。
References
