题解：P4387 【深基15.习9】验证栈序列

· · 题解

简化题目

这个题目实际上有很多要注意的地方，所以我们先尝试从简单的类似问题入手。

以下文段可以在我的博客里阅读 验证栈序列

输入一个 n ,表示有 1\sim n 的元素要入栈

第二行 n 个数,表示需要判断的出栈序列

第一种情况:

第 i 个元素 x 是当前最大值，那么这个 x 是一定可以成功入栈并出栈的,但是在原来的模拟算法中,我们是把 x 元素之前的元素全部入栈,这里浪费了一部分时间

那我们来思考是不是只用记录 x-1 即可呢?

答案是肯定的,因为出栈只需要不断地判断栈顶,所以我们只需要维护栈顶

但是如果 x-1 已经出栈就不用考虑了,因为如果 x 为最大值,那么前 i-1 个数中的最大值就是 x-1 ,也就是说 x-1 时我们已经维护过栈顶了,又不用考虑 x-1 所以此时什么也不用做

第二种情况：

即第 i 个元素不是最大值,那么不一定可以直接出栈,所以我们要判断这个数是不是我们维护的栈顶,如果不是就证明出栈序列不成立;如果是的话我们就要弹出这个数并更新新的栈顶(更新操作与之前同理)

特殊情况:

比如 n=6 时:

出现 2,6 ...时

按照上述算法会发现,当判断 2 时维护的栈顶是 1,但 6 时维护的却是 5,那我们应该按哪个为准呢?

显然,应该先让 5 为准,但是 1 也需要记录,形成了一个先进后出的原则,也就是实际维护栈顶需要栈来完成

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];


bool check(int n){
    bool s[100005];//记录i是否已经合法出栈 
    stack<int>q;//储存当前栈顶元素  
    int maxx=0;//记录最大值
    for(int i=1;i<=n;i++){
        if(a[i]>maxx){//最大值一定可以入栈并出栈 
            maxx=a[i];
                //特别的，a[i]==1时不能记录1-1即0
            if(!s[a[i]-1]&&a[i]>1)q.push(a[i]-1);//记录栈顶 
            s[a[i]]=1;
        }
        else{
            if(q.empty()){//栈空也可以正常弹出
                s[a[i]]=1;
                if(!s[a[i]-1]&&a[i]>1)q.push(a[i]-1);
                continue;
            }
            if(q.top()==a[i]){
                q.pop();
                s[a[i]]=1;
                if(!s[a[i]-1]&&a[i]>1)q.push(a[i]-1);
                continue;
            }
            return 0;
        }
    }
    return 1;
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<check(n);

    return 0;
}

针对本题的解法

从刚才的算法中我们解决了元素为 1 到 n 的问题,那该如何解决本题呢?

实际上本题也可以转化为 1 到 n ,只是这里的 1 到 n 代表的是元素下标

我选择的是一种简单但时间复杂度比较高的方法:

map映射大法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
bool s[100005];//记录i是否已经合法出栈 


bool check(int n){
    stack<int>q;//储存当前栈顶元素 
    memset(s,0,sizeof(s));
    int maxx=0;
    for(int i=1;i<=n;i++){
        if(a[i]>maxx){//最大值一定可以入栈并出栈 
            maxx=a[i];
            if(!s[a[i]-1]&&a[i]>1)q.push(a[i]-1);//记录栈顶 
            s[a[i]]=1;
        }
        else{
            if(q.empty()){
                s[a[i]]=1;
                if(!s[a[i]-1]&&a[i]>1)q.push(a[i]-1);
                continue;
            }
            if(q.top()==a[i]){
                q.pop();
                s[a[i]]=1;
                if(!s[a[i]-1]&&a[i]>1)q.push(a[i]-1);
                continue;
            }
            return 0;
        }
    }
    return 1;
}
map<int,int>mp;
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        mp.clear();
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            mp[x]=i;
        }
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++){
            a[i]=mp[a[i]];
        }
        if(check(n))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

    return 0;
}