Leetcode 155 最小栈

双栈解法：

class MinStack {
public:
    MinStack(){

    }
    
    void push(int val) {
        st.push(val);
        if(min_st.empty()) {     
            min_st.push(val);
        }else {
            int tmp = val <= min_st.top() ? val : min_st.top();
            min_st.push(tmp);
        }
        
    }
    
    void pop() {
        st.pop();
        min_st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }

private:
    stack<int> st;
    stack<int> min_st;
};

单栈解法

此解法也是跟别人学习的，栈里存差值的解法，关于栈里存pair的其实在空间上并没有什么优化，而且那个代码也很简单，要进一步优化，还是得明白这个代码

class MinStack {
public:
    MinStack() : min_num(INT_MAX){

    }
    
    void push(int val) {
        if (st.empty()) {
            st.push(0);
            min_num = val;
        } else {
            long long sub = val -min_num;
            // 栈中存放当前值与最小值的差值
            st.push(sub);
            // 如果差值小于0，代表当前val比当前最小值更小
            if (sub < 0) {min_num += sub;}
        }
    }
    
    void pop() {
        long long top_ = st.top();
        st.pop();
        // 如果栈顶元素小于0，说明上一个最小值是比现在最小值要大的，也就是说最小值是更新了的， 否则就是最小值没变
        min_num = top_ < 0 ? min_num - top_ : min_num;
    }
    
    int top() {
        // 跟上面理解差不多，如果栈顶元素小于0，代表栈顶元素就是最小值
        if (st.top() <= 0) {return min_num;}
        else {return min_num + st.top();}
    }
    
    int getMin() {
        return min_num;
    }

private:
    stack<long long> st;
    long long min_num;
};