题目链接:https://leetcode-cn.com/problems/min-stack/
题目大意
略。并且题目中要求的操作都要 O(1) 实现。
分析
用 2 个栈,一个普通栈,一个单调栈。
代码如下
class MinStack {
public:
/** initialize your data structure here. */
stack< int > sk;
stack< int > minsk; // 从栈底到栈顶递增的单调栈 MinStack() { } void push(int x) {
sk.push(x);
if(!minsk.empty() && x > minsk.top()) minsk.push(minsk.top());
else minsk.push(x);
} void pop() {
//assert(!sk.empty() && !minsk.empty());
sk.pop();
minsk.pop();
} int top() {
//assert(!sk.empty());
return sk.top();
} int getMin() {
//assert(!minsk.empty());
return minsk.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();
*/