题目：剑指 Offer 30. 包含min函数的栈 - 力扣（Leetcode）

题目的接口：

class MinStack {
public:/** initialize your data structure here. */MinStack() {}void push(int x) {}void pop() {}int top() {}int min() {}
};/*** 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();*/

解题思路：

这道题的思路很巧妙，

我的思路是，通过建立两个栈来实现这个能够做到O(1)取最小值的栈。

如果一个栈正常压栈出栈，

一个栈用来放最小值，每次有最小值就放进去，

然后这是代码：

class MinStack {
public:MinStack() {}void push(int val) {_st.push(val);//如果出现<=之前的数据if(_minST.empty() || _minST.top()>=val){_minST.push(val);}}void pop() {if(_st.top()==_minST.top())_minST.pop();        _st.pop();}int top() {return _st.top();}int getMin() {return _minST.top();}
private:stack<int> _st;stack<int> _minST;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

但是我当时做题的时候一下子脑子没转过来，

没用上面那种思路，

就想着简化一下出栈的操作，就想改进一下这个思路：（其实没必要，两种思路差别不大）

就每次入栈都入一遍，

出栈一起出就行，就不用判断是不是最小值再出。

代码如下：

代码：

class MinStack {
public:/** initialize your data structure here. *///建两个栈stack<int> st_push;stack<int> st_min;MinStack() {}void push(int x) {//正常入栈st_push.push(x);//如果是空就直接入栈if(st_min.empty()){st_min.push(x);}//如果遇到更小的值就改变入栈的值else if(st_push.top() < st_min.top()){st_min.push(st_push.top());}else//如果没遇到更小的值就再入一次{st_min.push(st_min.top());}}void pop() {//直接同时出栈st_push.pop();st_min.pop();}int top() {return st_push.top();}int min() {return st_min.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();*/