关于验证栈序列O(n)做法的常数优化

· · 算法·理论

一般算法(模拟)

模拟栈的压入与弹出，理论上每个元素最多要经过一次入栈一次出栈，大概在 T(n)\approx2n

改进算法

输入一个 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;
}

感谢各位dalao的观看，代码可以正常过P4387验证栈序列，如果有不对之处或可改进之处欢迎反馈！