题解 | #包含min函数的栈#

题目难度：简单
考察点：栈
简要说明：题目要求O(1)实现栈并且要实现输出栈内最小值，前面可以直接用栈来实现，要取出栈内最小值可以格外定义一个栈保存当前的最小值

具体思路
定义两个栈a,b，前者为普通的栈，后者用来存储最小值
1.压入栈（value）,a直接压入value，对于b，要压入value和b.top()较小的一个
为什么正确呢？会在弹出的时候给出证明

 void push(int value) {
        a.push(value);//将value压入a
        if(!b.size())b.push(value);//b为空时直接压入value
        else{
                //此时栈不空，压入min（b.top(),value）
        if(value>=b.top())
            b.push(b.top());
        else b.push(value);
        }
    }

2.弹出栈
首先给出证明

根据证明，弹出操作就很好写了，

 void pop() {
        a.pop();//弹出a栈顶元素
        b.pop();//弹出b栈顶元素
    }

3.返回栈顶
返回a栈顶即可

int top() {
        return a.top();//返回a栈顶
    }

4.返回min
返回b栈顶即可

int min() {
        return b.top();
    }

复杂度分析
每次压入，弹出操作都是O(1)的，所以时间复杂度O(1)
用了两个栈保存元素和栈内最小值，所以空间复杂度O(n)
整体代码

class Solution {
    stack<int>a,b;//定义栈a保存元素，栈b保存最小值
public:
    void push(int value) {
        a.push(value);//将value压入a
        if(!b.size())b.push(value);//b为空时直接压入value
        else{
                //此时栈不空，压入min（b.top(),value）
        if(value>=b.top())
            b.push(b.top());
        else b.push(value);
        }
    }
    void pop() {
        a.pop();//弹出a栈顶元素
        b.pop();//弹出b栈顶元素
    }
    int top() {
        return a.top();//返回a栈顶
    }
    int min() {
        return b.top();//返回b栈顶
    }
};