剑指Offer_30_包含min函数的栈

❗️LeetCode_155_最小栈

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：各函数的调用总次数不超过 20000 次

解法1：

/**
 * 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();
 */
class MinStack {
public:

    stack<int> s;  //主栈
    stack<int> Mins;  //辅助栈，用来保存最小值

    MinStack() {

        //因为辅助栈保存的是最小值，所以要初始化成最大的数
        Mins.push(INT_MAX);
    }
    
    void push(int x) {

        s.push(x);  //主栈元素入栈
    
        //辅助栈元素入栈，入的是辅助栈栈顶和已入主栈元素两者中的最小值
        Mins.push(std::min(Mins.top(), x));  //min要加命名空间，因为下面重写了min
    }
    
    void pop() {
        
        s.pop();  //主栈栈顶元素出栈
        
        Mins.pop();  //辅助栈也必须同步将栈顶元素出栈
    }
    
    int top() {

        return s.top();  //返回主栈的栈顶元素
    }
    
    int min() {

        return Mins.top();  //返回主栈的最小值即辅助栈此时的栈顶元素
    }
    
};