题解 | #栈的压入、弹出序列# 用数组模拟栈

class Solution {
  public:
    // 我的做法 最后 19/20。。。
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        // if (pushV.size() == 0) return false;

        // stack<int> st;

        // int m = pushV.size(), n = popV.size();

        // int pt1 = 0, pt2 = 0;
        // st.push(pushV[pt1]);
        // bool flag = true;
        // while (!st.empty() || pt1<m) {
        //     if(st.empty() && pt1<m)
        //     {
        //         pt1++;
        //         st.push(pushV[pt1]);
        //         continue;
        //     }
        //     int t = st.top();
        //     if (t != popV[pt2]) {
        //         pt1++;
        //         if (pt1 >= m) {
        //             flag = false;
        //             break;
        //         }
        //         st.push(pushV[pt1]);

        //     } else {
        //         st.pop();
        //         pt2++;
        //     }
        // }

        // return flag;

        // 官解2 不使用栈 直接用数组模拟
        
        int n = popV.size();
        int m = 0; // 时刻表示栈顶
        int pt2 = 0;
        for(int pt1=0; pt1<n; ++pt1)
        {
            //加入栈顶
            pushV[m] = pushV[pt1];
            // 出栈 非空 且栈顶定于 popV
            while(m>=0 && pushV[m]==popV[pt2])
            {
                //出栈
                m--;
                pt2++;

            }
            m++;// 该遍历下一个
        }

        // 顺利遍历完 就 Ok
        return m==0;
    }
};

空间复杂度 1