排队动物

题目

人其实是一种"排队动物"。

新学期到了，同学们都需要去排队注册，小J和小R相约一起去了二基楼。到了二基楼，发现由于堆放了杂物，走廊变得特别狭窄，只能站下一个人，同学们已经排起了长队。想要离开队伍的同学只能从队尾离开。

小R问小J："你说要是有同学不断前来，他们如果突然不想排队了，能以怎样的顺序离开呢？"

小J这一次学聪明了，他没急着答应小R："我可以告诉你我猜是怎样的，你来看看对不对吧。"

所有同学都拥有一个数字编号，他们将以特定的顺序进入队伍，每一次只有在队尾的同学才可以离开，请你帮助小R判断他们是否可以以小J猜测的顺序离开。

输入：第一行一个整数 q，询问次数。接下来 q 个询问，对于每个询问：第一行一个整数 n 表示队伍长度；第二行 n 个整数表示入队序列；第三行 n 个整数表示出队序列。
输出：对于每个询问，可以输出 YES，不可以输出 N0。

样例1：

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

YES
N0

样例2：

2
6
1 2 3 4 5 6
4 6 5 3 2 1
5
1 2 3 4 5
3 5 4 1 2

YES
N0

思路

用栈模拟入队过程：先把入队序列和出队序列都读进来，然后逐个压栈，每压入一个元素就立刻检查栈顶是否等于当前待出队的目标——等于就弹出并移动指针，不等于就继续压。全部压完后若栈为空则输出 YES，否则输出 N0。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int q;
    cin>>q;
    for(int c=0;c<q;c++){
        int n;
        stack<int> s;
        int order=0;

        cin>>n;
        vector<int> in(n);
        for(int c1=0;c1<n;c1++)
            cin>>in[c1];
        vector<int> out(n);
        for(int c2=0;c2<n;c2++)
            cin>>out[c2];

        for(int c1=0;c1<n;c1++){
            s.push(in[c1]);
            while(!s.empty()&&s.top()==out[order]){
                s.pop();
                order++;
            }
        }
        if(s.empty()) cout<<"YES"<<endl;
        else cout<<"N0"<<endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(q × n)，每个元素最多入栈、出栈各一次。
• 空间复杂度：O(n)，栈和两个数组的额外空间。

← 返回菜鸟的coding