传送门→

就是实现一个能在常数时间内返回最小值的栈。
根据常规思维，减少时间开销的代价一般都是增大空间开销，所以往这个方向去思考。因为栈可能随时都在弹出元素，所以单纯的用一个变量去维护最小值是不够的，这里可以用另一个栈来辅助。

单独设置一个栈mini用以保存当前栈顶元素进栈时的最小值，即每一个新元素进站时从此元素与当前mini栈顶元素中得到较小值，在x进栈的同时将这个最小值压入mini栈。这样mini栈顶就一定是当前栈内的最小值。

class MinStack {
protected:
    vector<int> data;
    vector<int> mini;
public:
    /** initialize your data structure here. */
    MinStack() {
        mini.push_back(INT_MAX);
    }
    
    void push(int x) {
        int tmp = min(mini.back(), x);
        data.push_back(x);
        mini.push_back(tmp);
    }
    
    void pop() {
        if(data.empty()) return;
        data.pop_back();
        mini.pop_back();
    }
    
    int top() {
        if(data.empty()) return 0;
        return data.back();
    }
    
    int getMin() {
        if(data.empty()) return 0;
        return mini.back();
    }
};

习惯地用了vector来模拟栈，当然用stack只会更方便。