题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
题解
用了一个栈来进行 pop, push 和 top 操作，一个整型用来保存最小值。pop 操作时需要借助另一个临时的栈，来处理最小值被弹出的情况。
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 {
stack<int> st;
int minItem;
public:
MinStack() {
}
void push(int x) {
if(st.empty())minItem=x;
st.push(x);
if(x<minItem)minItem=x;
}
void pop() {
int k=st.top();
st.pop();
if(k==minItem&&!st.empty())
{
minItem=st.top();
stack<int> tmp;
while(!st.empty())
{
int t=st.top();
minItem=t<minItem?t:minItem;
tmp.push(t);
st.pop();
}
while(!tmp.empty())
{
st.push(tmp.top());
tmp.pop();
}
}
}
int top() {
return st.top();
}
int getMin() {
return minItem;
}
};
|
执行用时：48 ms, 在所有 C++ 提交中击败了51.38%的用户
内存消耗：14.7 MB, 在所有 C++ 提交中击败了41.60%的用户