【Leetcode算法题】155. 最小栈

By Long Luo

155. 最小栈题目如下:

  1. 最小栈

设计一个支持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操作总是在 非空栈 上调用。

方法一:暴力

思路与算法:

的数据结构先进后出

所以我们需要一个链表来存储数据,并排好序,这样获取最小值的时候,直接读取链表的第一个元素即可。

代码如下所示:

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
class MinStack {

Stack<Integer> stack;
List<Integer> list;

public MinStack() {
stack = new Stack<>();
list = new ArrayList<>();
}

public void push(int val) {
stack.push(val);
list.add(val);
Collections.sort(list);
}

public void pop() {
int val = stack.peek();
stack.pop();
for (int i = 0; i < list.size(); i++) {
if (list.get(i).intValue() == val) {
list.remove(i);
break;
}
}
Collections.sort(list);
}

public int top() {
return stack.peek();
}

public int getMin() {
return list.get(0);
}
}

复杂度分析:

  • 时间复杂度:对于题目中的push和pop操作,时间复杂度均为O(nlogn)O(n logn),因为需要进行排序;其他操作都是O(1)O(1)
  • 空间复杂度:O(N)O(N),其中NN为总操作数。

方法二:辅助栈

思路与算法:

方法一时间复杂度太高,而且占用空间也不小,需要进行优化。

因为栈是先进后出的,所以可以在每个元素aa入栈时把当前栈的最小值minmin存储起来。在这之后无论何时,如果栈顶元素是aa,我们就可以直接返回存储的最小值minmin

因此我们可以使用一个辅助栈,与元素栈同步插入与删除,用于存储与每个元素对应的最小值。

当一个元素要入栈时,我们取当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中;

当一个元素要出栈时,我们把辅助栈的栈顶元素也一并弹出;

在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中。

代码如下所示:

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
class MinStack {

Stack<Integer> numStack;
Stack<Integer> minStack;

public MinStack_min() {
numStack = new Stack<>();
minStack = new Stack<>();
minStack.push(Integer.MAX_VALUE);
}

public void push(int val) {
numStack.push(val);
minStack.push(Math.min(numStack.peek(), minStack.peek()));
}

public void pop() {
numStack.pop();
minStack.pop();
}

public int top() {
return numStack.peek();
}

public int getMin() {
return minStack.peek();
}
}

复杂度分析:

  • 时间复杂度:对于题目中的所有操作,时间复杂度均为O(1)O(1)。因为栈的插入、删除与读取操作都是O(1)O(1),我们定义的每个操作最多调用栈操作两次。
  • 空间复杂度:O(N)O(N),其中NN为总操作数。最坏情况下,我们会连续插入n个元素,此时两个栈占用的空间为O(n)O(n)