[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\)。
因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
当要入栈一个元素时，获取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
代码如下所示：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
39
40
41class MinStack_2Stack {
Stack<Integer> numStack;
Stack<Integer> minStack;
// time: O(1)
public MinStack_2Stack() {
numStack = new Stack<>();
minStack = new Stack<>();
}
// time: O(1)
public void push(int val) {
numStack.push(val);
if (!minStack.empty()) {
int top = minStack.peek();
if (val < top) {
minStack.push(val);
}
} else {
minStack.push(val);
}
}
// time: O(1)
public void pop() {
int pop = numStack.pop();
if (pop == minStack.peek()) {
minStack.pop();
}
}
// time: O(1)
public int top() {
return numStack.peek();
}
// time: O(1)
public int getMin() {
return minStack.peek();
}
}
复杂度分析：
- 时间复杂度：
- \(\texttt{push()}\): \(O(1)\)。
- \(\texttt{pop()}\): \(O(1)\)。
- \(\texttt{top()}\): \(O(1)\)。
- \(\texttt{getMin()}\): \(O(1)\)。
- 空间复杂度：\(O(N)\)，其中 \(N\) 为总操作数。
方法三：一个栈
思路与算法：
方法二使用了两个栈去实现，那么我们能不能用一个栈去实现呢？
当然可以！
我们可以只用一个变量 \(min\) 去保存最小值，但问题是如果只用一个变量就会遇到下列情况：
如果把\(min\)更新为最新的更小值，那之前的最小值就丢失了。
怎么把之前的最小值保存起来？我们可以把它压入栈中，然后在出栈时，如果出栈元素是最小元素时，先把当前最小值出栈，然后再出栈一次。
代码如下所示：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
36static class MinStack_min {
Stack<Integer> stack;
int min = Integer.MAX_VALUE;
// time: O(1)
public MinStack_min() {
stack = new Stack<>();
}
// time: O(1)
public void push(int val) {
if (val <= min) {
stack.push(min);
min = val;
}
stack.push(val);
}
// time: O(1)
public void pop() {
if (stack.pop() == min) {
min = stack.pop();
}
}
// time: O(1)
public int top() {
return stack.peek();
}
// time: O(1)
public int getMin() {
return min;
}
}
复杂度分析：
- 时间复杂度：
- \(\texttt{push()}\): \(O(1)\)。
- \(\texttt{pop()}\): \(O(1)\)。
- \(\texttt{top()}\): \(O(1)\)。
- \(\texttt{getMin()}\): \(O(1)\)。
- 空间复杂度：\(O(N)\)，其中 \(N\) 为总操作数。
小结
这道题除了上述方法之后，还可以有其他诸如链表等，可以参考下 这里 。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗