题解 | 栈的压入、弹出序列

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> s;
        int cnt = 0;
        for(int i = 0; i < popV.size(); ++i){
            int val = popV[i];
            while(s.empty()||s.top()!=val){
                //在最开始就不允许已经出完的栈继续压入，最好写在while的判断中，但是那样有点长我就写在这里了
                if(cnt==pushV.size())   break;
                s.push(pushV[cnt]);
                ++cnt;
            }
            if(s.top()!=val) return false;
            s.pop();
        }
        return true;
    }
};

方法一：

辅助栈，如果栈顶不是就往后看，如果一直没有看到就失败了。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        int len = pushV.size();
        int pos1=-1, pos2=-1;
        for(const int& u:popV){
            while(pos1==-1||pushV[pos1]!=u){
			  //在最开始就不允许已经出完的栈继续压入，最好写在while的判断中，但是那样有点长我就写在这里了
                if(pos2==len) break;
                ++pos1, ++pos2;
                pushV[pos1] = pushV[pos2];
            }
            if(pushV[pos1]!=u) return false;
            --pos1;
        }
        return true;
    }
};

方法二：

原理和方法一相同，只是利用了已经入栈的位置不会再用，数量只会和栈中的元素一样或者更多，能够放下栈此时有的所有元素。

可以节约空间。

相比官方解法，不在循环内部修改循环数组是比较安全的做法。

两个方法的时间复杂度都是O(n)，方法一的空间复杂度是O(n)，方法二的空间复杂度是O(1)。