AcWing 41. 包含min函数的栈
原题链接
简单
作者:
我要出去乱说
,
2021-02-02 09:47:02
,
所有人可见
,
阅读 391
class MinStack {
public:
/** initialize your data structure here. */
stack<int> stackmin; //维护一个单调栈,储存最小值
stack<int> stackval;
MinStack() {
}
void push(int x) {
stackval.push(x);
if (stackmin.empty() || x <= stackmin.top()) //若push的值小于单调栈最小值,则同时push入单调栈
stackmin.push(x);
}
void pop() {
if (stackval.top() == stackmin.top()) //若pop的值等于单调栈最小值,则同时pop单调栈
stackmin.pop();
stackval.pop();
}
int top() {
return stackval.top();
}
int getMin() {
return stackmin.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();
*/