题目

输入样例1：

4
3 2 4 1

输出样例1：

7

输入样例2：

5
3 4 2 5 1

输出样例2：

9

样例解释

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

思路

主要注意理解几点：

• 一个排列中的每个数只会出现一次。
• 这里的连续数列是指连续的正整数。

找到用于优化时间复杂度的性质：在一个元素个数为R - L + 1区间 [L, R] 内，如果区间的最大值和最小值的差为 R - L，那么该区间是连号区间。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 10010, INF = 1e5;
int a[N];

int main()
{
  int n;
  cin >> n;
  
  for (int i = 0; i < n; i ++)
  {
    cin >> a[i];
  }
  
  int res = 0;
  
  for (int i = 0; i < n; i ++)
  {
    //每次更新左端点i,都要重置maxx, minx
    int maxx = -INF, minx = INF;

    for (int j = i; j < n; j ++)
    {
      maxx = max(maxx, a[j]), minx = min(minx, a[j]);
      if (maxx - minx == j - i)res ++;
    }

  }
  
  cout << res;
  return 0;
}