思路:枚举左右端点,找出区间内的最大值和最小值,如果相减等于区间大小,那么这区间就满足条件
优化:
我们在枚举的时候发现,如果最大值减去最小值大于了n-左端点的值,那么后面即使每个数都是我们想要组成连号区间的数也是无法满足的,所以说这个左端点的右端点就不用继续往后枚举了
列如:
3 4 2 5 1
在我们枚举到左端点为2,然后右端点为5时,此时区间内的maxv为5,minv为2
这个时候我们发现maxv-minv==3,我们至少需要3个数才能组成连号区间,而后面最多只能填一个数了,所以说就不用继续往后枚举了
优化代码为maxv-minv>n-l(左端点即为枚举时的i);
//y总代码,枚举每个左右端点
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, INF = 100000000;
int n;
int a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int res = 0;
for (int i = 0; i < n; i ++ ) // 枚举区间左端点
{
int minv = INF, maxv = -INF;
for (int j = i; j < n; j ++ ) // 枚举区间右端点
{
minv = min(minv, a[j]);
maxv = max(maxv, a[j]);
if (maxv - minv == j - i) res ++ ;
}
}
cout << res << endl;
return 0;
}
//优化代码
#include<iostream>
using namespace std;
int a[10010],n,ans;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{ int mx=0,my=1e9;
for(int j=i;j<=n;j++)
{
mx=max(mx,a[j]);
my=min(my,a[j]);
if((mx-my)>(n-i)) break;//优化操作,实现原理如上
if((mx-my)==(j-i)) ans++;
}
}
cout<<ans<<endl;
return 0;
}
最后附上优化前后的运行时间对比