avatar

day17_155_最小栈

题目

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入:
["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.

提示:

  • poptopgetMin 操作总是在 非空栈 上调用。

Related Topics

  • 设计

解答

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
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;

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

public void push(int x) {
stack.push(x);
if (!minStack.isEmpty()) {
int top = minStack.peek();
//小于的时候才入栈
if (x <= top) {
minStack.push(x);
}
}else{
minStack.push(x);
}
}

public void pop() {
int pop = stack.pop();

int top = minStack.peek();
//等于的时候再出栈
if (pop == top) {
minStack.pop();
}

}

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

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

}

//runtime:6 ms
//memory:41 MB
文章作者: 无知的小狼
文章链接: https://bytedance.press/2020/05/11/20200501/day17_155_%E6%9C%80%E5%B0%8F%E6%A0%88/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 无知的小狼

评论