题目描述
设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); --> Returns -4.
minStack.pop();
minStack.top(); --> Returns 3.
minStack.getMin(); --> Returns -1.
算法1
(一个栈实现) $O(1)$
声明一个最小值保持栈中的最小值,栈中保留的是当前值与最小值的差值,分情况采用不同处理
C++ 代码
class MinStack {
public:
typedef long long LL;
stack<LL> stk;
LL min_value;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if(stk.empty()){
stk.push(x);
min_value = x;
}else{
stk.push(x - min_value);
min_value = min((LL)x, min_value);
}
}
void pop() {
if(stk.top() < 0 ){
min_value -= stk.top();
}
stk.pop();
}
int top() {
if(stk.size() == 1){
return stk.top();
}else if(stk.top() > 0){
return min_value + stk.top();
}else{
return min_value;
}
}
int getMin() {
return min_value;
}
};
/**
* 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();
*/