[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
30
155. 最小栈

设计一个支持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
39
class 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(nlogn)\),需要进行排序。
    • \(\texttt{pop()}\): \(O(nlogn)\)
    • \(\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
41
class 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
36
static 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. 😉😃💗