LeetCode155|剑指 Offer 30. 包含 min 函数的栈

调用 min、push 及 pop 的时间复杂度都是 O(1)

因此实现一个能够得到栈的最小元素的 min 函数，我们就不能使用for等循环去查找，直接去排序大可不必，所以我们可以通过创建另一个栈，专门去存储每次比较的最小值。

新建两个栈数据结构，stack<int> s;stack<int> sort;

实现push加入函数，s就正常加，而sort里加每次比较后的最小值，最小值依旧在栈顶。

void push(int x) {
        s.push(x);
        if(!sort.empty()){
            int num = sort.top()<x?sort.top():x;
            sort.push(num);
        }else{
            sort.push(x);
        }
    }

pop删除函数也有需要注意的地方

情况一：

sort和s栈顶元素都是最小值

我们一旦删除了s中的最小值，那么sort这个栈顶元素本身不存在了，为了做出同步，所以两个栈都需要删除。

情况二：

sort是最小值，s栈顶是非最小值，会不会有错误呢？

我们以，-2，0，-3，4压入为例，如果我们同步删除两个栈的栈顶，-3被删除了，4被删除了，貌似最小值被我们删除了，可是你别忘记我们所写的push，最小值不止存入了一次，压入4之前，sort栈顶元素是-3，压入4时，4大于-3，因此，又一个-3被压入，删的只是本次比较的-3，之前的-3还是在栈中，不要忘记sort压入的是每次比较后的最小值，不是只有一个。

top函数不用多说，直接返回s的栈顶，min函数的实现方式则是返回sort的栈顶，sort栈顶永远是最小值。

完整代码

class MinStack {
public:
    stack<int> s;
    stack<int> sort;
    /** initialize your data structure here. */
    MinStack() {
    }
    void push(int x) {
        s.push(x);
        if(!sort.empty()){
            int num = sort.top()<x?sort.top():x;
            sort.push(num);
        }else{
            sort.push(x);
        }
    }
    void pop() {
        s.pop();
        sort.pop();
    }
    int top() {
        return s.top();
    }
    int min() {
        return sort.top();
    }
};