Leetcode115.最小栈

题目要求维护一个栈，除了支持普通栈的压栈，查顶，弹出操作外，还需支持一个O(1)的查询栈内最小元素的操作

可以这么思考这个问题:

定义一个普通的栈s，一个保存当前栈s的最小元素的栈sMin，对于压栈和弹出操作，他们两个保持同步

对于一个新压入的元素x，如果x大于等于现在已知的栈内最小元素，则x对于最小元素是没有贡献的，有没有他都一样，所以压入s，sMin压入当前sMin.top()，用于保持两个栈的元素同步，以维护弹出操作，此时可以说我们维持现状

对于小于当前已知的栈内最小元素x，应当同时压入两个栈中，此时可以说更新答案

class MinStack {
public:
    stack<int> s;
    stack<int> sMin;

    MinStack() {
        ;
    }

    void push(int val) {
        if (s.empty()) {
            s.push(val);
            sMin.push(val);
        }else if (val < sMin.top()) {
            // 更新答案
            s.push(val);
            sMin.push(val);
        } else {
            // 维持现状
            s.push(val);
            sMin.push(sMin.top());
        }
    }

    void pop() {
        s.pop();
        sMin.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};