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

class Solution {
public:
    void push(int value) {
        s1.push(value);
        //空或者新元素较小，则入栈
        if(s2.empty() || s2.top()>value)
            s2.push(value);
        else
            //重复加入栈顶
            s2.push(s2.top());
    }
    void pop() {
        //如果当前s1栈顶是最小元素，则s2栈顶也是最小元素，都要删除
        //如果当前s1栈顶不是最小元素，则s2栈顶是重复的最小元素，也要删除，使两个栈的大小保持一致，这样当s1长度为0时，s2也为0，便于对s2进行管理
        s1.pop();
        s2.pop();
    }
    int top() {
        return s1.top();
    }
    int min() {
        return s2.top();
    }
private:
    //用于栈的push 与 pop
    stack<int> s1;
    //用于存储最小min
    stack<int> s2;
};

思路：用另外一个栈来存储最小值

我们都知道栈结构的push、pop、top操作都是O(1)，但是min函数做不到，于是想到在push的时候就将最小值记录下来，由于栈先进后出的特殊性，我们可以构造一个单调栈，保证栈内元素都是递增的，栈顶元素就是当前最小的元素。

具体做法：

• step 1：使用一个栈记录进入栈的元素，正常进行push、pop、top操作。
• step 2：使用另一个栈记录每次push进入的最小值。
• step 3：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶。