题目描述

太难被屏蔽了

样例

6
3
6
0
9
6
3



2

时间复杂度

O(n)

参考文献

yxc

C++ 代码

#include<bits/stdc++.h>
#include<limits.h>
#define PII pair<int,int>
using namespace std;
const int N=200010;
const int MAX=1e9+10;
int n;
PII a[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    int res=1,last=INT_MAX,next=-1;
    int j;
    for(int i=1;i<=n;)
    {
        j=i;
        while(j<=n&&a[j].first==a[i].first) j++;
        int minp=a[i].second;
        int maxp=a[j-1].second;
        if(next==-1)
        {
            if(last>maxp) last=minp;
            else next=1,last=maxp;
        }
        else
        {
            if(last<minp) last=maxp;
            else res++,next=-1,last=minp;
        }
        i=j;
    }
    cout<<res<<endl;
    return 0;
}

–