包含min函数的栈

思路：（双栈法）

1.由于对于pop（）、top（）、push（）操作，直接用现有的stack中的这些操作就行，因为时间复杂度是O（1）

2.但是对于stack中现有的min函数，时间复杂度不是O（1）

3.所以可以通过另一个栈进行辅助记录栈1中的最小值，则栈2的栈顶元素就是栈1中的最小值

4.每次将插入栈1的元素与栈2的栈顶元素大小进行比较，将如果新的值小，就将该值压入栈2，否则就把栈2的栈顶元素本身压入栈中

代码：

class Solution {
public:
//想在栈原先的结构中增加求min的函数，又要求时间复杂度是O（1）
//对于pop()、top()、push()操作中本生的stack的这些操作的时间的复杂度就是O（1），所以可以直接调用
//但是需要另一个栈来保留栈中的最小的元素
//则每次插入的时候，就将插入栈1的元素与栈2的栈顶元素进行大小比较
//如果发现当前的值比栈2的栈顶的值小，就将该值也压入栈2，即更新栈2的栈顶元素为当前栈1中的最小值
//否则就表示当前栈2的栈顶元素还是最小值，就直接将栈2的栈顶元素再一次插入栈2
//则栈2的栈顶的元素就是栈1中min
    stack<int>s1;
    stack<int>s2;
    void push(int value) {
        s1.push(value);
        if(s2.empty()||s2.top()>value){
            s2.push(value);
        }else{
            s2.push(s2.top());
        }
    }
    void pop() {
        s1.pop();
        s2.pop();
    }
    int top() {
        return s1.top();
    }
    int min() {
        return s2.top();
    }
};