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

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:

    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        if (pushV.size() != popV.size()) {
            return false;
        }

        vector<int> mStack;

        int j = 0;
        //经过pushV.size()，检验全部入栈元素
        for (int i = 0; i < pushV.size(); i++) {
            if (pushV[i] == popV[j]) {
                //直接出栈
                j++;
                while((!mStack.empty()) && (mStack[mStack.size() - 1] == popV[j])){
                    mStack.pop_back();
                    j++;
                }
            } else if (mStack.size() == 0) {
                //栈为空，入栈
                mStack.push_back(pushV[i]);
            } else if (mStack[mStack.size() - 1] == popV[j]) {
                //栈顶元素出栈，并将新元素入栈
                mStack.pop_back();
                mStack.push_back(pushV[i]);
                j++;
                while((!mStack.empty()) && (mStack[mStack.size() - 1] == popV[j])){
                    mStack.pop_back();
                    j++;
                }
            } else {
                mStack.push_back(pushV[i]);
            }

            // printStack(mStack);
        }


        //检查剩余元素
        for (int i = mStack.size() - 1; i >= 0; i--) {
            if (mStack[i] != popV[j]) {
                return false;
            }
            j++;
            // printStack(mStack);
        }

        return true;

    }


    void printStack(vector<int> myStack){
        string str ="mystack:[";
        for(auto num:myStack){
            str+= to_string(num)+",";
        }
        str+="]";
        cout<<str<<endl;
    }
};