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

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;

        // 官解1
        
        stack<int> st;
        int m = pushV.size(), n = popV.size();
        int pt1 = 0;
        for(int pt2=0; pt2<n; ++pt2)
        {
            // 入栈 栈空 或者栈顶不等于当前pt2指向的元素
            while((st.empty() || st.top()!=popV[pt2]) && pt1<m)
            {
                st.push(pushV[pt1]);
                pt1++;
            }

            // 相等 就出栈
            if(st.top()==popV[pt2])
            {
                st.pop();
            }
            else
            {
                //其余情况 都不对

                return false;
            }
        }

        // 顺利遍历完 就 Ok
        return true;
    }
};

O（n ） O(n) 对栈的理解

错题集