题目链接
1210. 连号区间数 - AcWing题库
一些话
流程
在 1∼N
的某个排列中有多少个连号区间呢？
求连号区间的个数，
求……个数问题
首先将区间枚举出来，再判断是否连号即可
关于连号区间
正常有序的连号区间比如
1，2，3，4，区间的边界值即区间的最小值与最大值，且差值与左右边界指针相关
由此，判断区间是否连号，首先要将区间的最大值和最小值找出来，判断其差值是否等于左右边界指针差值即可
n<1e5,可以用
for(int i = 0;i < n;i++){
for(int j = i;j < n;j++){
}
}
枚举区间
时间复杂度n*n/2,
套路
单个数组区间的枚举 O（n * n / 2)
1. for(int i = 0;i < n;i++){ 2. for(int j = i;j < n;j++){ 3. 4. } 5. }
2.连号区间判断
if(maxn - minn == j - i)
ac代码
// 8:35~8:40思考 // ~52调试 //~59 accepted //9:01 ~ #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 1e4 + 10,INF = 0x3f3f3f3f; int f[N]; int n; int main(){ cin >> n; for(int i = 0;i < n;i++){ scanf("%d",&f[i]); } int ans = 0; for(int i = 0;i < n;i++){ int maxn = -INF,minn = INF; for(int j = i;j < n;j++){ minn = min(minn,f[j]); maxn = max(maxn,f[j]); if(maxn - minn == j - i) ans++; } } cout << ans << endl; }
