友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
-
MinStack()初始化堆栈对象。 -
void push(int val)将元素val推入堆栈。 -
void pop()删除堆栈顶部的元素。 -
int top()获取堆栈顶部的元素。 -
int getMin()获取堆栈中的最小元素。
示例 1:
输入： ["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.
提示：
-
-231 <= val <= 231 - 1 -
pop、top和getMin操作总是在 非空栈 上调用 -
push,pop,top, andgetMin`最多被调用 `3 * 104次
思路分析
使用两个栈，一个栈存原始数据，另外一个栈存当前栈的最小值。
不比每次都向最小栈里面添加数据，只在出现更小值的时候才向最小栈中添加数据。如下图：
-
一刷
-
二刷
-
三刷
-
四刷
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
66
67
68
69
70
71
72
/**
* Runtime: 8 ms, faster than 18.94% of Java online submissions for Min Stack.
* Memory Usage: 46.2 MB, less than 5.08% of Java online submissions for Min Stack.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-24 16:40
*/
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> helper;
/**
* initialize your data structure here.
*/
public MinStack() {
stack = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (helper.isEmpty() || x < helper.peek()) {
helper.push(x);
} else {
helper.push(helper.peek());
}
}
public void pop() {
stack.pop();
helper.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return helper.peek();
}
// Runtime: 10 ms, faster than 14.80% of Java online submissions for Min Stack.
// Memory Usage: 46.6 MB, less than 5.08% of Java online submissions for Min Stack.
// private Stack<Integer> stack;
// private PriorityQueue<Integer> queue;
//
// /**
// * initialize your data structure here.
// */
// public MinStack() {
// stack = new Stack<>();
// queue = new PriorityQueue<>();
// }
//
// public void push(int x) {
// stack.push(x);
// queue.add(x);
// }
//
// public void pop() {
// Integer value = stack.pop();
// queue.remove(value);
// }
//
// public int top() {
// return stack.peek();
// }
//
// public int getMin() {
// return queue.peek();
// }
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-24 16:40
*/
class MinStack {
private Deque<Integer> stack = new LinkedList<>();
private Deque<Integer> minStack = new LinkedList<>();
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-31 16:09:25
*/
public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else {
if (x < minStack.peek()) {
minStack.push(x);
} else {
minStack.push(minStack.peek());
}
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-31 16:09:25
*/
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> min;
public MinStack() {
stack = new LinkedList<>();
min = new LinkedList<>();
}
public void push(int val) {
stack.push(val);
if (min.isEmpty() || val < min.peek()) {
min.push(val);
} else {
min.push(min.peek());
}
}
public void pop() {
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-31 22:38:19
*/
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> min;
public MinStack() {
stack = new ArrayDeque<>();
min = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if (min.isEmpty() || val <= min.peek()) {
min.push(val);
} else {
min.push(min.peek());
}
}
public void pop() {
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}