每日算法打卡：连号区间数

算法
767 words

原题链接

1210. 连号区间数

题目难度：简单

题目来源：第四届蓝桥杯省赛C++ B组,第四届蓝桥杯省赛Java B组

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 $1 \sim N$ 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 $[L, R]$ 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 $R-L+1$ 的“连续”数列，则称这个区间连号区间。

当 N 很小的时候，小明可以很快地算出答案，但是当 NNN 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 N，表示排列的规模。

第二行是 N 个不同的数字 $P_i$，表示这 N 个数字的某一排列。

输出格式

输出一个整数，表示不同连号区间的数目。

数据范围

$1 \le N \le 10000$,
$1 \le P_i \le N$

输入样例1：

1
2
4
3 2 4 1

输出样例1：

1
7

输入样例2：

1
2
5
3 4 2 5 1

输出样例2：

1
9

样例解释

第一个用例中，有 7 个连号区间分别是：$[1,1], [1,2], [1,3]$, [1,4], [2,2], [3,3], [4,4]
第二个用例中，有 9 个连号区间分别是：$[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]$

题目分析

题目的意思就是求1到n的连续子区间的个数，要注意的就是这个排列的顺序是不可改变的，而且每个数字只出现一次

最暴力的做法就是枚举所有的子区间，然后再判断区间是否是连续的，这样的做法大概就是$O(n^3\log n)$

然后来想一下如何优化，我们首先考虑这个判断的过程是否可以优化，那么一个区间是连号区间有什么样的性质，其实对于一个连号区间，必然是满足最大值减最小值等于子区间左右两个下标相减的，所以这个连号区间的条件就可以等价于最大值与最小值的差是否满足子区间左右下标相减

那么我们如何获取最大值和最小值呢，实际上是可以在第二次循环的过程中就顺便算出来的，因为每一次获取一个新的数据，就可以对已有数据进行比较，取较大或者较小的那个数字即可

这样做的时间复杂度就是$O(n^2)$

示例代码

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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 10010, INF = 1e8;

int n;
int arr[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    
    int ans = 0;
    for(int i=0;i<n;i++) // 枚举区间左端点
    {
        int Min = INF, Max = -INF;
        for(int j=i;j<n;j++)
        {
            Min = min (Min,arr[j]);
            Max = max(Max,arr[j]);
            if(Max-Min==j-i) ans++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}
Comments