当前位置 博文首页 > 中流击水，浪遏飞舟：双栈&&剑指 Offer 30. 包含min函数
大佬的力扣题解精选链接
大佬的图让我翻然醒悟：（下面是大佬的图
首先需要一个主栈来完成除min()外的基本操作；
用一个辅助栈来完成min()的操作，辅助栈存储的是主栈的非严格降序元素，所以辅助栈的top()一直都是主栈的最小值！而且只有在主栈空的时候辅助栈才会空！push()中辅助栈的if中小于等于是为了存储重复数字！
原先自己写的O(n)时间查找stack< int >最小值的方法超时了且不符合题意，需要O(1)时间查找栈的最小值
class MinStack {
public:
/** initialize your data structure here. */
stack<int> a;
stack<int> b;
MinStack() {
}
void push(int x) {
a.push(x);
if(b.empty()||b.top()>=x){
b.push(x);
}
}
void pop() {
if(b.top()==a.top()){
b.pop();
}
a.pop();
}
int top() {
return a.top();
}
int min() {
return b.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->min();
*/
