设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
除了维护一个一个栈的基本操作外,还需要维护一个单调栈用来获取最小值,对于单调栈而言如果插入的元素stackmin.top()>=x就吧该元素插入栈中,否则不插入栈中
当取出一个元素时即进行pop操作时如果从stackValue取出的元素等于stackmin中栈顶的元素时,一起取出
class MinStack {
public:
/* initialize your data structure here. /
stack[HTML_REMOVED] stackValue,stackmin;
MinStack() {
}
void push(int x) {
stackValue.push(x);
if(stackmin.empty()||stackmin.top()>=x){
stackmin.push(x);
}
}
void pop() {
if(stackValue.top()==stackmin.top()){
stackmin.pop();
}
stackValue.pop();
}
int top() {
return stackValue.top();
}
int getMin() {
return stackmin.top();
}
};