LeetCode 155. 最小栈 题解
155. 最小栈#
https://leetcode.cn/problems/min-stack/
https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
我们找个用例看看:依次入栈-2 0 -3
。
1
2
3
4
5
6
7
8
|
[-2,0,-3]
对应最小值:
[-2,-2,-3]
出栈-3
[-2,0]
对应最小值:
[-2,0]
|
依次入栈0 1 0
。
1
2
3
4
5
6
7
8
|
[0,1,0]
对应最小值:
[0,0,0]
出栈0
[0,1]
对应最小值:
[0,0]
|
可以发现最小值需要一个容器维护,由于每次取出顺序与写入顺序相反,符合栈的性质。
使用另一个容器同步维护当前栈顶对应最小值#
我们尝试用一个栈存原数据,用另一个栈维护对应下标最小值。
两个栈的数据量保持一致。
复杂度分析#
- push
- stackFull 写入原数据
- stackMini 写入 min(当前数据,stackMini.peek)
- 基于数组或者链表的插入复杂度均为
O(1)
- pop
- getMini
使用了额外的栈维护对应最小值,空间占用O(n)
。
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
42
43
44
45
46
|
public class MinStack2 {
/**
* stackMini将局部最小值以与stackFull等量的方式存储
*/
Stack<Integer> stackFull;
Stack<Integer> stackMini;
public MinStack2() {
stackFull = new Stack<>();
stackMini = new Stack<>();
}
public int pop() {
Integer top = stackFull.pop();
if (top == null) {
throw new IllegalStateException();
}
stackMini.pop();
return top;
}
public void push(int val) {
stackFull.push(val);
if (stackMini.isEmpty()) {
stackMini.push(val);
} else {
Integer miniTop = stackMini.peek();
int mini = val <= miniTop ? val : miniTop;
stackMini.push(mini);
}
}
public int getMin() {
return stackMini.peek();
}
public int top() {
return stackFull.peek();
}
public void clear() {
stackFull.clear();
stackMini.clear();
}
}
|
这种思路下,我们可以有另外一种写法,使用一个栈维护出入栈操作,节点内部同步维护当前值、当前对应最小值。
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
|
public class MinStack3 {
Stack<int[]> stack;
// 使用一个栈存储,内部存数据,0位存原数字,1位存对应最小值
public MinStack3() {
stack = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new int[]{val, val});
} else {
int[] prev = stack.peek();
int smaller = val < prev[1] ? val : prev[1];
stack.push(new int[]{val, smaller});
}
}
public int pop() {
// 数组同步跟随stack出栈
return stack.pop()[0];
}
public int getMin() {
return stack.peek()[1];
}
public int top() {
return stack.peek()[0];
}
public void clear() {
stack.clear();
}
}
|
使用另一个容器只维护当前写入更小的元素#
说起来有点拗口,解释起来就是,前面的做法我们的stackMini
其实会存储与stackFull
等数据量的数据,不难发现其中有很多值是重复的。
比如:
1
2
3
|
[0,1,2]
对应最小值:
[0,0,0]
|
增量序列,其实我们只需要维护一个最小值即可。
也就是入栈出栈我们需要判断这个逻辑:
- 递增序列:
- 入栈:
stackMini
不入栈新数据,stackMini
空则需要入栈;
- 出栈:出到
stackMini
栈顶数据大小的时候,stackMini
出栈
- 递减序列:
- 入栈:
stackMini
入栈新数据(因为新数据更小!!)
- 出栈:因为出去的是比栈顶更小的数据,所以需要出栈,
stackMini
以此来追逐stackFull
的步伐
- 相等序列:
- 入栈:
stackMini
也需要加入一个相同的元素,不加入后面出栈很难搞
- 出栈:出到
stackMini
栈顶数据大小的时候,stackMini
出栈
还需要把入栈出栈逻辑整理一下:
- 入栈:
stackMini
空则需要入栈;
- 递增不入栈;
- 递减、相等序列均入栈;
- 出栈:
- 出到
stackMini
栈顶数据大小的时候,stackMini
出栈;
复杂度分析#
同前方案。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
public class MinStack {
/**
* 执行用时:
* 4 ms
* , 在所有 Java 提交中击败了
* 93.20%
* 的用户
* 内存消耗:
* 43.4 MB
* , 在所有 Java 提交中击败了
* 24.46%
* 的用户
* 通过测试用例:
* 31 / 31
*/
Deque<Integer> stackFull;
// 存储局部最小元素
Deque<Integer> stackMini;
public MinStack() {
stackFull = new LinkedList<>();
stackMini = new LinkedList<>();
}
/**
* stackFull 不管怎样,都要push
* stackMini空,插入第一个最小元素,当前值小于mini顶,插入
*/
public void push(int val) {
stackFull.push(val);
if (stackMini.isEmpty() || stackMini.peek() >= val) {
stackMini.push(val);
}
}
public int top() {
if (stackFull.isEmpty()) {
return -1;
}
return stackFull.peek();
}
public int pop() {
Integer val = stackFull.pop();
// 如果出栈了当前mini顶最小的元素,mini跟着出栈
if (!stackMini.isEmpty() && stackMini.peek().equals(val)) {
stackMini.pop();
}
return val == null ? -1 : val;
}
public int getMin() {
if (stackMini.isEmpty()) {
return -1;
}
return stackMini.peek();
}
public void clear() {
stackFull.clear();
stackMini.clear();
}
}
|
这道题使用这种思路出错概率大一点。但是在n
比较大规模的时候会节省不少空间。利弊参半。
Ref#