[Leetcode][155. 最小栈] 3种方法：辅助列表，辅助栈，单栈
By Long Luo
Leetcode 155. 最小栈 题目如下：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
30155. 最小栈
设计一个支持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操作总是在 非空栈 上调用。
这道题有很多方法可以做，其实也就分为额外 \(O(n)\) 和 \(O(1)\) 空间，如果 \(O(n)\) 的话，有非常多方法。如果只能使用一个栈的话，需要思考如何处理当前 \(\texttt{push()}\) 更小的数如何处理。
方法一：栈 + List
思路与算法：
最开始想到的方法就是用一个链表存储数据，这样排序之后获取最小值的就直接读取链表的第一个元素即可。
代码如下所示：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
36
37
38
39class MinStack {
Deque<Integer> stack;
List<Integer> numList;
public MinStack() {
stack = new ArrayDeque<>();
numList = new ArrayList<>();
}
// time: O(nlogn)
public void push(int val) {
stack.push(val);
numList.add(val);
Collections.sort(numList);
}
// time: O(n)
public void pop() {
int val = stack.pop();
for (int i = 0; i < numList.size(); i++) {
if (numList.get(i) == val) {
numList.remove(i);
break;
}
}
Collections.sort(numList);
}
// time: O(1)
public int top() {
return stack.peek();
}
// time: O(1)
public int getMin() {
return numList.get(0);
}
}
复杂度分析
- 时间复杂度：
- \(\texttt{push()}\): \(O(n \log n)\)，需要进行排序。
- \(\texttt{pop()}\): \(O(n \log n)\)。
- \(\texttt{top()}\): \(O(1)\)。
- \(\texttt{getMin()}\): \(O(1)\)。
- 空间复杂度：\(O(N)\)，其中 \(N\) 为总操作数。
方法二：辅助栈
思路与算法：
方法一时间复杂度太高，其实排序也是不必要的，占用空间也不小。
因为栈是先进后出的，所以可以在每个元素 \(x\) 入栈时把当前栈的最小值 \(min\) 存储起来。
在这之后无论何时，如果栈顶元素是 \(x\)，我们就可以直接返回存储的最小值 \(min\)。
因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
当要入栈一个元素时，获取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。