最长连续段 题解

题目分析

我们需要在可以任意重排数组的前提下，找出数组中最长的连续段子数组。

连续段的定义是：一个数组 $b$ 满足 $b_{i+1} = b_i + 1$，也就是说数组中的元素必须是严格递增且相邻差值为 $1$ 的整数序列。例如 [2, 3, 4] 是连续段，而 [2, 4]、[2, 2, 3] 都不是。

由于我们可以随意重排原数组，因此我们不必关心元素在原数组中的位置，只需要关心哪些数值出现了以及能否用它们拼出最长的连续整数序列。

值得注意的是，如果某个数值在原数组中出现了多次，在连续段中也只能使用其中一个，因为连续段要求相邻两个数相差 $1$，不能相等。

所以问题转化为：
从原数组的所有不同数值中，选出一个最长的值域连续（相邻差为 $1$）的序列，这个序列的长度就是答案。

解题思路

1. 排序与去重
   先将数组从小到大排序，这样相邻的数就会靠在一起。排序后遍历数组，跳过重复出现的数值，相当于我们只关心每个数值是否“存在”。

2. 求最长连续递增段
   在排序去重后的序列中，寻找最长的子段，满足 $a'_i + 1 = a'_{i+1}$。
   我们可以用一个变量 cnt 记录当前连续段的长度，另一个变量 mx 记录全局最大长度。

   • 如果当前数值等于上一个数值（重复），直接跳过，不影响当前连续段。
   • 如果当前数值恰好比上一个数值大 $1$，则当前连续段可以延伸，cnt++。
   • 否则，连续段中断，cnt 重置为 $1$（以当前数值作为新段的起点）。

3. 输出答案
   遍历结束后，mx 就是最长连续段的长度。

算法说明

以输入样例 [1, 0, 2, 4] 为例：

• 排序后得到 [0, 1, 2, 4]
• 遍历：
  • 0：last = 0, cnt = 1, mx = 1
  • 1：比 last 大 $1$，cnt = 2, mx = 2, last = 1
  • 2：比 last 大 $1$，cnt = 3, mx = 3, last = 2
  • 4：不是 last+1，cnt = 1, last = 4
• 最终 mx = 3，对应连续段 [0, 1, 2]，重排时将它们放在一起即可得到长度为 $3$ 的连续段子数组。

时间复杂度分析

• 排序需要 $O(n \log n)$ 的时间。
• 遍历去重并求最长连续段只需 $O(n)$。
• 总体时间复杂度为 $O(n \log n)$，在 $n \le 10^5$ 的数据范围内可以高效运行。
• 空间复杂度为 $O(n)$ 或 $O(1)$（取决于排序是否使用额外空间，一般快排为 $O(\log n)$）。

参考代码

cpp
复制
1#include <algorithm>
2#include <cstdio>
3using namespace std;
4
5const int N = 1e5 + 5;
6int n;
7int a[N];
8
9int main() {
10    scanf("%d", &n);
11    for (int i = 1; i <= n; i++) 
12        scanf("%d", &a[i]);
13    
14    // 1. 排序
15    sort(a + 1, a + n + 1);
16    
17    int last = a[1];   // 上一个有效数值
18    int cnt = 1;       // 当前连续段长度
19    int mx = 1;        // 全局最大长度
20    
21    // 2. 遍历数组，跳过重复并统计连续段
22    for (int i = 1; i <= n; i++) {
23        if (a[i] == last) 
24            continue;              // 重复数值，跳过
25        if (a[i] == last + 1) {
26            cnt++;                 // 连续，延伸
27        } else {
28            cnt = 1;               // 中断，重置
29        }
30        last = a[i];               // 更新上一个有效数值
31        mx = max(cnt, mx);         // 更新最大值
32    }
33    
34    printf("%d\n", mx);
35    return 0;
36}

代码解释

• 输入与排序：读入 $n$ 和数组 $a$，使用 sort 将数组从小到大排序。
• 初始化：last 记录上一个被纳入统计的数值，初始化为排序后的第一个元素；cnt 记录当前连续段长度，至少为 $1$；mx 记录答案。
• 遍历：
  • 若 a[i] == last，说明是重复元素，直接跳过，既不延长也不中断连续段。
  • 若 a[i] == last + 1，说明可以和前一个数构成连续递增，cnt 加 $1$。
  • 否则，数值不连续，以当前元素作为新段的起点，cnt 重置为 $1$。
  • 每步更新 last 和 mx。
• 输出：循环结束后 mx 即为答案。

总结

本题的关键在于理解“可任意重排”带来的自由度——我们实际上只需要关注数值的存在性，而无需考虑原数组的顺序。通过排序和一次线性扫描，就能高效求出最长连续值域段的长度，整个过程清晰且时间复杂度优秀。