题解 | 验证栈序列

#include <iostream>
// #include<stack>
#include<vector>
using namespace std;
// #define test for(int ai:an) {cout << ai << ' ';}cout << '\n'
int main() {
    int q;cin>>q;
    while(q--){   
    int n ; cin >> n;
    vector<int> an = {0}; // 入栈序列
    vector<int> pos(n+1,1); // 判断出栈
    int ai_1 , ai_2;
    for(int _ = 0;_<n;_++){
        cin >> ai_1;
        an.push_back(ai_1);
    }
    int pos_ = 1;
    bool flag = true;
    for(int _ =0;_<n;_++){
        cin >> ai_2; 
        while(true){
            if(pos_ > n){ // 不能得到出栈队列
                flag = false;
                break;
            }
            if(an[pos_] != ai_2 ) {pos_++;continue;} //进行出栈匹配
            pos[an[pos_]] = 0;
            pos_--;
            while(true){ // 找下一个要出栈的
                if (pos[an[pos_]] == 0 && pos_ > 0)pos_--; // 被出栈的继续回退 
                else break; 
            }
            // test;
            break;
        }
        }
    if(flag){
        cout << "Yes"<<'\n';    
    }else cout << "No" << '\n';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

分享一个不用栈的办法,欢迎大家提出建议