作者：LeetCode-Solution
链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/solution/bao-han-minhan-shu-de-zhan-by-leetcode-s-i2fk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法一：辅助栈

要做出这道题目，首先要理解栈结构先进后出的性质。
对于栈来说，如果一个元素a在入栈时，栈里有其他的元素b, c, d，那么无论这个栈在之后经历了什么操作，只要a在栈中，b, c, d就一定在栈中，因为在a被弹出之前，b，c，d不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是a，那么我们就可以确定栈里面现在的元素一定是a, b, c, d。
那么，我们可以在每个元素a入栈时把当前栈的最小值m存储起来。在这之后无论何时，如果栈顶元素是a，我们就可以直接返回存储的最小值m。

算法

按照上面的思路，我们只需要设计完成一个数据结构，使得每个元素a与其相应的最小值m时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入或删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中。
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一起弹出。
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        s2.push(INT_MAX);
    }
    
    void push(int x) {
        s1.push(x);
        if(x <= s2.top()){
            s2.push(x);
        }
    }
    
    void pop() {
        if(s1.top() == s2.top()){
            s2.pop();
        }
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int min() {
        return s2.top();
    }
private:
    stack<int> s1;
    stack<int> s2;
};

/**
 * 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();
 */