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

思路：

第一想法就是：依次从左往右遍历两个数组来维护一个栈；

• 遍历入栈数组时判断当前元素值是否等于出栈元素当前值：

1. 若相等则栈出栈，并且两个数组均向右移动到下一个元素；
2. 若不相等则栈入栈当前入栈数组元素，入栈数组向右移动到下一个元素；
3. 这样就模拟出了栈出入栈的过程，当遍历结束后，只要判断维护的栈是否是空的即可得到结果。

代码如下：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int psz=pushV.size();
        int posz=popV.size();
        if(psz==0 && posz==0) return true;//若两个数组均为空返回true
        if(psz==0 || posz==0) return false;//若只有其中一个数组为空，则返回false
        stack<int> stk1;//维护一个栈
        int i=0;int j=0;
        while(i<psz && j<posz){//遍历终点时遍历完两个数组中的其中一个即可
            while(i<psz && (stk1.empty() || stk1.top()!=popV[j])){    // 入栈
              //遍历时条件判断从左至右依次是数组下标不越界、栈为空时、栈不为空且栈顶元素不等于当前出栈元素时
                stk1.push(pushV[i++]);//入栈后下标右移
            }
            while(j<posz && !stk1.empty() && stk1.top()==popV[j]){   //  出栈
              //遍历时条件判断从左至右依次是数组下标不越界、栈不为空时、栈顶元素等于当前出栈元素
                stk1.pop();  //出栈
                j++;  //  下标右移
            }
        }
        return stk1.empty();   //返回最后维护的栈是否为空即可
    }
};

• 时间复杂度： 因为要遍历完两个数组所有元素，所以时间复杂度为O(N+N),即O(N);
• 空间复杂度： 维护了一个栈，最大消耗空间为N个元素占用空间，因此空间复杂度为O(N)