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();
    }
};