GESP 题解库 / 4 级题解 / [GESP202509 四级] 最长连续段 · 第 5 / 25 题
GESP202509 四级 · B4416 · 简单

最长连续段

数组可任意重排,求重排后"相邻恰差 1"的子数组最长长度。

📊
n ≤ 10⁵
数组长度
🔢
aᵢ ≤ 10⁹
数值范围
⚡
O(n log n)
时间复杂度
🎯
去重 + 找最长连续整数区间
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

对于 k 个整数构成的数组 [b₁, b₂, …, b_k],如果对任意 1 ≤ i < k 都有 b(i+1) = b(i) + 1,则称它是一个连续段。

给定数组 a,你可以任意重排它的元素顺序。问重排后,所有是连续段的子数组中,最长的长度是多少。

💡
人话翻译:连续段要求"后一个恰好比前一个大 1",所以段内元素必须互不相同且恰好连成一段(比如 3、4、5、6)。重排能让我们把这些数排到一起,所以问题就变成了:数组里最长的一段"连续整数"有多长。

🔍 关键词提取

重排去重连续整数区间排序

已知条件

项目说明
输入第一行 n;第二行 n 个整数
输出重排后最长连续段的长度
数据范围n ≤ 10⁵
数值范围−10⁹ ≤ aᵢ ≤ 10⁹,可能为负
子数组必须下标连续;重排指的是先重排整个数组再取子数组

需要解决的问题

02
思维导图
整理解题思路的全貌
🔗 重排 → 去重 → 找最长连续区间
🧠 核心转化
连续段要求相邻差 1
所以段内元素互不相同
重排可自由安排顺序
等价于"找最长连续整数区间"
📥 处理数组
排序(去重更简单)
或排序后用 unique
也用 set 去重
aᵢ 可能为负
🔍 扫描统计
维护当前链长 cur
若 a[i] == a[i−1] → 跳过
若 == a[i−1]+1 → cur++
否则 cur 重置为 1
⚠️ 易错点
忘记去重
把"差 1"写成"差不大于 1"
没处理负数
n = 1 的边界
03
样例手算推导
两个样例的转化过程

🧮 样例 1:数组 [1, 0, 2, 4]

先看"重排"能带来什么,再把它转化成找连续区间。

1
观察:重排能改变什么

原数组里 0、1、2 是连续的,但 4 插在中间

重排成 [4, 0, 1, 2] 后,后半段 0、1、2 就成了连续段

所以答案是 3

✅ 3

2
转化成"最长连续整数区间"

数组里的数去重后是 {0, 1, 2, 4}

其中 0、1、2 是连续的一段(长度 3)

4 单独一个,不接前面(2 和 4 之间缺了 3)

✅ 最长连续区间长度 = 3

排序去重后相邻差是否连续
0—起点
11✅ 连续
21✅ 连续
42❌ 断了

最长链:0 → 1 → 2,长度 3 ✓

🧮 样例 2:数组 [9, 9, 8, 2, 4, 4, 3, 5, 3]

这组数据里有很多重复(9 出现 2 次、4 出现 2 次、3 出现 2 次),正好考察"去重"。

步骤内容说明
原数组9, 9, 8, 2, 4, 4, 3, 5, 3有重复元素
排序2, 3, 3, 4, 4, 5, 8, 9, 9相同元素相邻
去重2, 3, 4, 5, 8, 9重复的只保留一个
找最长连续区间2 → 3 → 4 → 5(长度 4)8、9 是另一段(长度 2)

答案 4 ✓

🔑
为什么必须去重?假设数组是 [3, 3, 4],如果不做去重,排序后是 3, 3, 4,扫描时会看到"3 到 3 差 0"和"3 到 4 差 1",容易误算成长度 3。但连续段要求严格递增 1,两个 3 不可能同时出现在同一个连续段里,所以正确答案是 2(3, 4)。
04
解法对比
排序去重后扫描 vs 用 set 判断起点

⚔️ 解法对比

🟢 排序 + 去重 + 扫描(推荐) 推荐

排序后扫一遍,跳过重复元素,统计相邻差 1 的最长链

  • 时间 O(n log n)
  • 代码 10 行
  • 不需要额外容器
  • 负数也能正确处理
💡
扫描规则:如果 a[i] == a[i-1] 就跳过(去重);如果 a[i] == a[i-1] + 1 就让链长加一;否则链长重置为 1。

🟠 用 set 判断"是否是新链的起点"

把数放进 set,只从"x−1 不在 set 中"的数开始往后数

  • 平均时间 O(n)
  • 需要哈希容器
  • 思路巧妙但边界多
  • 处理负数/大值要注意
⚠️
优点:省掉排序的 log 因子;缺点:需要额外 set 空间,而且"从每个链的起点出发"这个逻辑不如扫描法直观。本题 n ≤ 10⁵,排序完全够快。

📈 性能对比

方案时间复杂度代码量
排序 + 扫描O(n log n)约 10 行
set 起点法期望 O(n)约 18 行
05
算法流程图
排序 → 去重 → 统计最长链
开始读入 n 和数组 a对 a 排序cur = 1,best = 1(记录当前链长与最优)i 从 1 到 n−1a[i] 与 a[i−1] 的关系?相等 → 跳过(去重)差 1 → cur 加 1其他 → cur 重置为 1best = max(best, cur)输出 best结束还有元素 → i 加 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔗 最长连续段计算器

输入一组整数,程序会排序去重并找出最长的连续整数区间。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

long long a[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

    sort(a, a + n);          // 排序后相同元素相邻,便于去重

    int best = 1, cur = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) continue;        // 重复元素跳过(相当于去重)
        if (a[i] == a[i - 1] + 1) cur++;       // 恰好差 1,链延长
        else cur = 1;                          // 断了,重新开始
        if (cur > best) best = cur;
    }

    printf("%d\n", best);
    return 0;
}
🔑
为什么"重复跳过"就够了?排序后相同元素一定相邻,遇到 a[i] == a[i-1] 时直接 continue,既不重置链长、也不延长,效果等同于"把重复元素删掉"。这比先手动 unique 再扫描更简洁。

📖 关键几行怎么看

代码作用为什么这样写
sort(a, a + n)排序让相同元素相邻,也让连续数相邻
if (a[i] == a[i-1]) continue;去重跳过重复,不影响当前链长
if (a[i] == a[i-1] + 1) cur++;链延长必须是恰好差 1
else cur = 1;链重置新的一段从这里开始
⚠️
三个坑:① 没做去重:[3, 3, 4] 会被误算成 3;② 把"差恰好 1"写成"差不大于 1",那样 [3, 3] 也会被算成长度 2;③ best 初始化为 0:当 n = 1 时会输出 0,应该是 1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 0 2 4
3题面样例 1
9
9 9 8 2 4 4 3 5 3
4题面样例 2(含大量重复)
1
7
1单元素,长度为 1
3
3 3 4
2必须去重:答案是 3、4 长度 2
3
3 3 3
1全相同,去重后只剩 1 个
5
5 4 3 2 1
5排序后恰好是 1~5,答案 5
4
-3 -2 -1 -5
3负数同样适用,−3、−2、−1 连续
✅
自查清单:① 去重了吗?② 判定是"恰好差 1"吗?③ 负数能处理吗(用 long long)?

🚨 易错点清单

⚠️
忘记去重:[3, 3, 4] 会被误判为 3。连续段要求严格递增 1,重复元素不可能在同一段内。
⚠️
把"差 1"写成"差不大于 1":那样相等的元素也会被并入,答案偏大。
⚠️
best 初始化为 0:n = 1 时会输出 0,正确的最小答案是 1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 1.7 × 10⁶

时间怎么算的?

空间都用在哪?

需要存下整个数组。

✅ 10⁵ 规模排序加扫描,瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 去重的三种写法
// 1) 排序 + 扫描时跳过(本题用法,最省事)
// 2) 排序 + unique
sort(a, a + n);
int m = unique(a, a + n) - a;      // m 是去重后的长度

// 3) 用 set 自动去重(值域大或稀疏时用)
set<long long> s(a, a + n);
for (long long x : s) { /* 已升序且无重复 */ }

// 找最长连续整数区间的"起点法"(不排序)
set<long long> st(a, a + n);
int best = 1;
for (long long x : st) {
    if (st.count(x - 1)) continue;   // 不是链起点,跳过
    long long y = x;
    while (st.count(y + 1)) y++;
    best = max(best, (int)(y - x + 1));
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
重排问题转化把"可重排"理解为"自由挑子集"所有"可重排后求最优"的题目
去重必要性连续段内不能有重复严格递增/递减序列类问题
排序 + 扫描相邻元素比较求最长连续、最长递增子序列(简化版)
🌟
思考题:如果题目改成"子序列(可以不连续)中最长的连续段",答案会变吗?(提示:不会变——因为我们可以重排整个数组,所以能不能连成一段只取决于"这些值是否都存在",与它们在原数组中的位置无关。这也是本题可以"先重排再取子数组"的原因。)