本场比赛难度吧不大，建议开题顺序为 \(T2-T1-T3\) 。
\(T2\)
题目描述
有 \(n\) 个高楼排成一行，每个楼有一个高度 \(h_i\)。称可以从楼 \(i\) 跳到 楼 \(j\)，当 \(i\), \(j\) ( \(i < j\) )满足以下三个条件之一：
-
\(i+1=j\)
-
\(\max(h_{i+1},h_{i+2},\cdots,h_{j-1})<\min(h_i,h_j)\)
-
\(\min(h_{i+1},h_{i+2},\cdots,h_{j-1})>\max(h_i,h_j)\)
现在你在楼 \(1\)，请求出跳到楼 \(n\) 最少要跳几次。
\(2 \leq n \leq 3\cdot 10^5\), \(1\leq h_i \leq 10^9\)。
思路点拨
没有什么思维的题。考虑动态规划，暴力转移显然是 $O(n^2) $ 的。
但是注意到条件 \(2,3\) 本质上是在描述序列的峰谷，我们知道这样的二元组 \((i,j)\) 的数量线性，所以使用单调栈求出。
时间复杂度线性。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+10;
int n,a[MAXN];
int f[MAXN];
int s1[MAXN],top1,s2[MAXN],top2;
signed main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
s1[++top1]=s2[++top2]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+1;
while(top1&&a[s1[top1]]<=a[i]){
int tmp=a[s1[top1--]];
if(a[i]!=tmp&&top1)
f[i]=min(f[i],f[s1[top1]]+1);
}
while(top2&&a[s2[top2]]>=a[i]){
int tmp=a[s2[top2--]];
if(a[i]!=tmp&&top2)
f[i]=min(f[i],f[s2[top2]]+1);
}//找出全部峰谷
s1[++top1]=s2[++top2]=i;
}
cout<<f[n];
return 0;
}