LeetCode155 Min Stack

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

样例

1
2
3
4
5
6
7
8
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.

思路

模拟一个栈,在常数时间内支持进栈push出栈pop输出栈顶元素top输出栈内最小元素getMin四种操作

我们知道,普通的栈对于前三种操作已经是常数时间了,但是如何实现常数时间内找到栈内最小元素呢?

可能一开始会想,不是可以$\mathcal{O}(1)$维护一个栈内最小元素的下标吗?getMin的时候直接根据下标输出不就好了

emm…是这样的没错。但是,一旦最小元素出栈后,我们就得找出栈内第二小元素来更新下标

这个该怎么处理呢,肯定不能把栈遍历一遍啊(时间复杂度不满足要求…


其实,只要维护一个单调栈即可(非严格单调递减),单调栈的栈顶就是原栈中最小的元素

其中stack A为原栈,stack B为辅助栈,# 表示栈底方向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
stack A: # | 10 |               // 元素10进栈
stack B: # | 10 | // 当前最小元素为10

stack A: # | 10 | 12 | // 元素12进栈
stack B: # | 10 | // 由于维护的是单调递减栈,当前最小元素仍然为10

stack A: # | 10 | 12 | 9 | // 元素9进栈
stack B: # | 10 | 9 | // 满足单调栈,当前最小元素更新为9

stack A: # | 10 | 12 | 9 | 14 | // 元素14进栈
stack B: # | 10 | 9 | // 不满足单调栈,当前最小元素仍为9

stack A: # | 10 | 12 | 9 | // 元素14出栈
stack B: # | 10 | 9 | // 不影响辅助栈,当前最小元素仍为9

stack A: # | 10 | 12 | // 元素9出栈
stack B: # | 10 | // 辅助栈栈顶的9同时出栈,当前最小元素更新为10

stack A: # | 10 | // 元素12出栈
stack B: # | 10 | // 不影响辅助栈,当前最小元素仍为10

代码

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
class MinStack {
private:
stack<int> a, b;
public:
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
// 原栈进栈的同时,看满不满足辅助栈的单调性质
if (b.empty() || x <= getMin()) b.push(x);
a.push(x);
}

void pop() {
// 原栈出栈的同时,看影不影响辅助栈的栈顶
if (a.top() == getMin()) b.pop();
a.pop();
}

int top() {
// 输出原栈的栈顶元素
return a.top();
}

int getMin() {
// 输出辅助栈栈顶元素,即为原栈中的最小元素
return b.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
分享到 评论