题目链接：https://www.acwing.com/problem/content/description/1212/
思路：考虑最暴力的写法 n^2 枚举区间 即起点和终点 然后将区间的数sort一遍
再判断一遍是否每个数都满足递增加1的关系
考虑如何去优化， 区间内的数排序后都要成递增的关系，那么 长度为R的区间 最大值减最小值就为R-1
再考虑如何去维护区间的最大值最小值，如果定下端点再去处理的话 那么复杂度也是n^3的
可以优化进第二重循环里面， 每次再新的一段左端点开始的时候，枚举右端点的时候就
等同于添加一个数进来，此时来维护mx 和mi 即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e4+10; 4 const int mod=1e9+7; 5 #define ll long long 6 #define ull unsigned long long 7 #define pi pair<int,int> 8 #define fi first 9 #define sc second 10 #define pb push_back 11 int a[maxn]; 12 13 14 15 int main() 16 { 17 ios::sync_with_stdio(false); 18 cin.tie(0); 19 int n; 20 cin>>n; 21 for(int i=1;i<=n;i++) cin>>a[i]; 22 int ans=0; 23 for(int i=1;i<=n;i++) 24 { 25 int mi=1e9,mx=-1e9; 26 for(int j=i;j<=n;j++) 27 { 28 mx=max(mx,a[j]); 29 mi=min(mi,a[j]); 30 if(mx-mi==j-i) ans++; 31 } 32 } 33 cout<<ans<<‘\n‘; 34 35 36 37 38 }
原文：https://www.cnblogs.com/winfor/p/14632471.html
