解析
记录一下每个数前面第一个比它大的和比它小的数的位置，然后从后往前跳。
先把比它大的找到，然后让比它小的在范围内向前跳，跳得越前越好。
每次跳完答案加一。
嗲吗
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define PII pair<int,int>
const int MOD=998244353;
const int N=300002;
const int M=998244353;
using namespace std;
inline int read(){register char c=getchar();register int s=0,f=1;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-'0';return s*f;}
int n;
int a[N];
int cnt1,cnt2;
int st1[N],st2[N];
int l[N],r[N];
int main(){
n=read();
st2[0]=-1;st1[0]=-2;
for(int i=1;i<=n;i++){
a[i]=read();
while(cnt1&&a[st1[cnt1]]>a[i])cnt1--;
while(cnt2&&a[st2[cnt2]]<=a[i])cnt2--;
l[i]=st1[cnt1];
r[i]=st2[cnt2];
st1[++cnt1]=st2[++cnt2]=i;
}
int ans=0;
int ll,rr=n;
while(rr>0){
ll=rr;
while(r[rr]<=l[ll])ll=l[ll];
ans++;
rr=ll-1;
}
printf("%d",ans);
return 0;
}
|