友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
-
push(x) — Push element x onto stack.
-
pop() — Removes the element on top of the stack.
-
top() — Get the top element.
-
getMin() — Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
思路分析
使用两个栈，一个栈存原始数据，另外一个栈存当前栈的最小值。
-
一刷
-
二刷
-
三刷
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
// 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
private Stack<Integer> stack;
private Stack<Integer> helper;
/**
* initialize your data structure here.
*/
public _0155_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
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();
}
}