题目理解
这道题可以任意重排数组,然后找最长的连续段(子数组里每个数都比前一个大 1)。
因为能重排,所以最优策略一定是把数组从小到大排序,然后找最长的连续整数序列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
核心思路
1. 排序:把数组从小到大排好,连续的数字会挨在一起。
2. 遍历统计:
* 如果当前数 = 前一个数 + 1 → 连续长度 +1
* 如果当前数 = 前一个数 → 重复数字,不打断连续,长度不变
* 如果数字不连续也不重复 → 连续长度重置为 1
3. 记录最大值:遍历过程中一直更新最长长度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
逐行代码精讲
* 万能头文件,包含所有需要的库(排序、输入输出等)。
* n:数组长度
* a[]:存数组的固定大小数组(不开 vector)
* 大小开 1e5+10 满足题目 n≤105n \le 10^5n≤105 的要求。
* 输入数组长度。
* 从 1 开始输入,数组下标从 1 开始用。
* 对数组从 a[1] 到 a[n] 排序。
* 排序后连续数字挨在一起,方便找最长连续段。
* x:最终答案(最长连续段长度)
* y:当前正在统计的连续段长度
* 初始都是 1,因为单个数字本身就是长度为 1 的连续段。
* 从第 2 个数开始遍历(要和前一个比较)。
* 连续 +1:当前连续长度 +1
* 更新最长答案 x。
* 不连续、不重复:连续中断,重置为 1
* 如果是重复数字,这里不执行,y 保持不变,不打断连续。
* 输出最长连续段长度,结束程序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例演算(超级清楚)
样例 1
输入:
排序后:0 1 2 4
遍历:
* i=2,a[2]=1 = 0+1 → y=2,x=2
* i=3,a[3]=2 = 1+1 → y=3,x=3
* i=4,a[4]=4 不连续 → y=1
最终输出:3
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例 2
输入:
排序后:2 3 3 4 4 5 8 9 9
遍历:
* 2→3 → y=2
* 3=3 → 不变
* 3→4 → y=3
* 4=4 → 不变
* 4→5 → y=4 (x=4)
* 5→8 中断 → 重置
* 后面不影响最大值
最终输出:4
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
为什么这代码是对的?
1. 重排 = 排序:想得到最长连续段,一定是排序后最优。
2. 重复数字不中断:题目允许重排,重复数字不破坏连续。
3. 线性遍历 O(n):速度极快,能过 10510^5105 大数据。