题目分析

这个题目考察我们对栈的理解和我们的思维能力，不难想到，希望小伙伴们可以先思考。

栈

我们只能利用两个栈，而且栈只可以取出顶部元素，无法进行排序，因此我们要好好使用它的性质。

因为每次push一个数，而不是将乱序的栈进行排序，这就给我们提供了思路。如果栈是有序的，那么再插入一个元素时有什么变化呢？如栈s是7，5，3，1。这时插入4，我们还想让栈是有序的，那么我们就需要将小于4的元素先存放起来，我们可以先存到另一个栈tmpS中，此时s：7，5，tmpS：1，3。这时我们可以将4加入到s中，再将tmpS中的元素取出放回到s中即可。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**，其中n为元素个数。

#include<iostream>
#include<stack>

using namespace std;

class SortedStack {
private:
    stack<int> s, tmpS;
public:
    SortedStack() {
        
    }

    void push(int val) {
        while (!s.empty() && s.top() < val) {
            tmpS.push(s.top());
            s.pop();
        }
        s.push(val);
        while (!tmpS.empty()) { 
            s.push(tmpS.top());
            tmpS.pop();
        }
    }

    void pop() {
        if (!s.empty()) { s.pop(); }
    }

    int peek() {
        return s.empty() ? -1 : s.top();
    }

    bool isEmpty() {
        return s.empty();
    }
};

优化栈

在上面的方法中，我们每次push都需要将小于val的元素都放入tmpS中，最后将tmpS中的元素再放回到s中。val的值非常大，那么每次都需要将所有元素弹出再插入一次，会浪费非常多的时间。

我们可以不将tmpS栈中的元素都压入s中。就保持s中的元素是大于等于val的，并且s是递减栈，而tmpS中的元素是递增的，且元素值都小于val。这样再插入下一个值k时，如果k >= val，我们就只用将s中小于k，大于等于val的值放入tmpS中即可，因为小于val的值已经放入tmpS中了，同理如果k < val，我们只用将tmpS中大于等于k，小于val的值放入s中即可，因为大于等于val的值已经放入s中了。

我们可以比较一下7，5，3，1插入2，4，6时，两个方法操作push和pop的次数。

方案一：tmpS压入1，s弹出1，s压入2，s压入1，tmpS弹出1。此时2插入完毕，push3次，pop2次。tmpS压入1，s弹出1，tmpS压入2，s弹出2，tmpS压入3，s弹出3，s压入4，s压入3，tmpS弹出3，s压入2，tmpS弹出2，s压入1，tmpS弹出1。此时4插入完毕，push7次，pop6次。tmpS压入1，s弹出1，tmpS压入2，s弹出2，tmpS压入3，s弹出3，tmpS压入4，s弹出4，tmpS压入5，s弹出5，s压入6，s压入5，tmpS弹出5，s压入4，tmpS弹出4，s压入3，tmpS弹出3，s压入2，tmpS弹出2，s压入1，tmpS弹出1。此时6插入完毕，push11次，pop10次。一共三次操作后，push21次，pop18次。

方案二：tmpS压入1，s弹出1，s压入2。此时2插入完毕，push2次，pop1次。tmpS压入3，s弹出3，s压入4。此时4插入完毕，push2次，pop1次。tmpS压入5，s弹出5，s压入6。此时6插入完毕，push2次，pop1次。一共三次操作后，push6次，pop3次。

但是要注意peek操作和pop操作。因为要获取全体元素的最小值，而最小值存放在tmpS栈中，因此要先将tmpS中的元素全部压入s中才能够peek和pop。

最坏情况下算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**，其中n为元素个数，但是绝大多数情况下都比第一种算法快得多。

#include<iostream>
#include<stack>

using namespace std;

class SortedStack {
private:
    stack<int> s1, s2;
public:
    SortedStack() {

    }

    void push(int val) {
        while (!s1.empty() && s1.top() < val) {
            s2.push(s1.top());
            s1.pop();
        }
        while (!s2.empty() && s2.top() >= val) {
            s1.push(s2.top());
            s2.pop();
        }
        s1.push(val);
    }

    void pop() {
        move();
        if (!s1.empty()) { s1.pop(); }
    }

    int peek() {
        move();
        return s1.empty() ? -1 : s1.top();
    }

    bool isEmpty() {
        return s1.empty() && s2.empty();
    }

    void move() {
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }
};

刷题总结

有趣的想法，方案二是我在看题解中发现的一种解法，非常非常的牛，因此介绍给小伙伴们学习。