题目地址:
https://www.acwing.com/problem/content/90/
设计一个支持push,pop,top等操作并且可以在
O
(
1
)
O(1)
O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
代码如下:
#include <stack>
using namespace std;
class MinStack {
public:
stack<int> stk, stk1;
MinStack() {
}
void push(int x) {
stk.push(x);
if (stk1.empty() || x <= stk1.top()) stk1.push(x);
}
void pop() {
if (stk.top() == stk1.top()) stk1.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return stk1.top();
}
};
所有操作时间复杂度 O ( 1 ) O(1) O(1)。