最长连续递增序列问题

题目描述：给定一个未排序的整数数组，找到最长连续递增序列的长度。这里的"连续递增"要求序列中的元素是严格递增的，且每个元素比前一个元素恰好大1。

解题思路分析：
这个问题要求找到最长的连续数字序列（每个数字比前一个数字大1），而不是简单的递增子序列。我们需要高效地确定数组中存在的连续数字段。

方法一：排序法（直观但非最优）

1. 如果数组为空，返回0
2. 对数组进行排序
3. 遍历排序后的数组，统计连续递增序列的长度
4. 记录遇到的最大长度

时间复杂度：O(nlogn) 主要来自排序
空间复杂度：O(1) 或 O(n)（取决于排序算法）

方法二：哈希集法（最优解）
核心思路：利用哈希集合实现O(1)的查找，避免重复计算

步骤详解：

1. 将数组所有元素存入哈希集合（去重且快速查找）
2. 遍历数组中的每个元素
3. 对于每个元素，如果它的前一个数（num-1）不在集合中，说明它是某个连续序列的起点
4. 从起点开始，逐个检查num+1, num+2...是否在集合中，统计序列长度
5. 更新最大长度

具体过程示例：
数组：[100, 4, 200, 1, 3, 2]

步骤1：构建哈希集合 {100, 4, 200, 1, 3, 2}

步骤2：遍历检查：

• 元素100：99不在集合中 → 是起点
  • 检查101, 102...都不在 → 序列长度=1
• 元素4：3在集合中 → 不是起点（跳过）
• 元素200：199不在集合中 → 是起点
  • 检查201, 202...都不在 → 序列长度=1
• 元素1：0不在集合中 → 是起点
  • 检查2在集合中 → 继续
  • 检查3在集合中 → 继续
  • 检查4在集合中 → 继续
  • 检查5不在集合中 → 序列长度=4
• 元素3：2在集合中 → 不是起点（跳过）
• 元素2：1在集合中 → 不是起点（跳过）

最终结果：最长连续序列长度为4（序列1,2,3,4）

代码实现：

def longest_consecutive(nums):
    if not nums:
        return 0
    
    num_set = set(nums)
    max_length = 0
    
    for num in num_set:
        # 只从序列起点开始计算
        if num - 1 not in num_set:
            current_num = num
            current_length = 1
            
            # 向后延伸序列
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1
            
            max_length = max(max_length, current_length)
    
    return max_length

复杂度分析：

• 时间复杂度：O(n)
  • 构建哈希集合：O(n)
  • 遍历过程：每个元素最多被访问两次（作为起点检查和在序列延伸时）
• 空间复杂度：O(n)（用于存储哈希集合）

关键优化点：

1. 去重处理：使用集合自动去重，避免重复元素影响
2. 避免重复计算：只从序列起点开始统计，确保每个连续序列只被计算一次
3. 快速查找：利用哈希集合的O(1)查找特性

这种方法相比排序法更加高效，特别是在处理大规模数据时优势明显。