单调栈,WA35分,求调!
查看原帖
单调栈,WA35分,求调!
688359
wangbo0楼主2023/8/18 17:06
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 300005
int n,a[N],ans1[N],ans2[N],tans=1;
stack<int>z;
signed main()
{
    ios::sync_with_stdio(0);cin.tie();cout.tie();
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!z.empty()&&a[i]>=a[z.top()])
            z.pop();
        if(z.empty())
            ans1[i]=0;
        else
            ans1[i]=z.top();
        z.push(i);
    }
    while(!z.empty())
        z.pop();
    for(int i=n;i>=1;i--)
    {
        while(!z.empty()&&a[i]<a[z.top()])
            z.pop();
        if(z.empty())
            ans2[i]=0;
        else
            ans2[i]=z.top();
        z.push(i);
    }
//  for(int i=1;i<=n;i++)
//      cout<<ans1[i]<<" ";
//  cout<<endl;
//  for(int i=1;i<=n;i++)
//      cout<<ans2[i]<<" ";
//  cout<<endl;
    int now=n;
    while(now)
    {
        if(ans1[now]!=0)
        {
//          cout<<now<<" "<<ans1[now]<<endl;
            tans++;
            for(int i=ans1[now];i<now;i++)
                if(ans2[i]>i||ans2[i]==0)
                {
                    now=i;
                    break;
                }
//          cout<<now<<endl;
        }
        else
        {
            int u=0;
            for(int i=1;i<now;i++)
                if(ans2[i]==0)
                {
                    u=1;
                    now=i;
                    break;
                }
            if(!u)
                now--;
        }
    }
    cout<<tans<<endl;
    return 0;
}
2023/8/18 17:06
加载中...