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

基本思路：用栈模拟，如果满足序列指针就在popV上右移，最后如果指针移到了popV末尾，就说明满足条件。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int i = 0, n = popV.size();
        for (auto &j: pushV) {
            st.push(j);
            while (!st.empty() && st.top() == popV[i]) {
                st.pop();
                i++;
            }
        }
        return i == n;
    }
};

优化思路：根据官方题解的思路对空间进行优化。因为栈本身就可以由数组实现，如果在pushV中实现栈，由于栈可能有出栈操作，栈顶指针的移动是一定比pushV的遍历要慢的，pushV只需要一次遍历，所以遍历过的元素覆盖了也无所谓。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int i = 0, j = 0, n = popV.size();
        for (auto &num: pushV) {
            pushV[i] = num;
            while (i >= 0 && pushV[i] == popV[j]) {
                i--;
                j++;
            }
            i++;
        }
        return i == 0;
    }
};