求1~n乱序数组中唯一连续递增子序列的最优复杂度解法（含计数与序列输出）

这是个挺有意思的问题，尤其是给定数组是1~n的乱序排列时，我们可以利用数值的天然连续性来设计时间复杂度O(n)、空间复杂度O(n)的最优解法，完全规避你之前思路里最坏O(n²)的问题。下面分两种场景详细说明：

一、仅统计符合要求的子序列数量 #

这里的核心观察是：每个符合要求的最大子序列的起始点，必然是满足「要么是1，要么它的前一个数值（x-1）在原数组中的位置比它更靠后」的元素。因为如果x-1在x后面，那我们无法在子序列中把x-1放在x前面形成连续递增的链，x只能作为新子序列的开头。

具体步骤：

1. 先构建一个位置映射数组pos，其中pos[x]表示数值x在原数组中的下标索引。因为数组是1~n的乱序，我们可以遍历原数组一次完成构建，时间O(n)，空间O(n)。
2. 遍历数值1~n，统计满足以下条件的x的数量：
   • x == 1，或者
   • pos[x-1] > pos[x]（x-1在原数组中出现在x之后）

这个统计结果就是符合要求的子序列总数。比如你给出的示例：
原数组[1,2,3,6,5,4,7,8,9]，pos数组为pos[1]=0, pos[2]=1, pos[3]=2, pos[6]=3, pos[5]=4, pos[4]=5, pos[7]=6, pos[8]=7, pos[9]=8。满足条件的x是1、5、6，共3个，和示例结果一致。

二、输出符合要求的子序列具体形式 #

在统计数量的基础上，我们可以顺着起始点往后延伸，找到每个子序列的所有元素：

1. 同样先构建pos数组。
2. 遍历数值1~n，找到所有起始点（即满足上述条件的x）。
3. 对于每个起始点x，依次往后找x+1, x+2,...，直到遇到某个y，满足y == n或者pos[y+1] > pos[y]（y+1在原数组中出现在y之后，无法继续延伸），收集这些数值就是一个完整的子序列。

还是用你的示例：

• 起始点1：依次检查1→2→3→4，到4时，pos[5]=4 < pos[4]=5？不，pos[5]=4比pos[4]=5小，说明5在4前面，无法把5接在4后面，所以子序列是[1,2,3,4]。
• 起始点5：检查5→6，pos[6]=3 < pos[5]=4，6在5前面，无法延伸，子序列是[5]。
• 起始点6：依次检查6→7→8→9，到9时没有后续数值，子序列是[6,7,8,9]。

整个过程每个数值只会被访问一次，时间复杂度O(n)，空间复杂度O(n)（存储pos数组和结果子序列）。

为什么这个解法比你之前的思路更优？ #

你之前的思路需要逐个检查已有子序列的末尾元素，最坏情况下（比如数组是n,n-1,...,1），每次都要新建子序列，检查次数是1+2+...+(n-1)，时间复杂度O(n²)。而我们利用数值的连续性，通过位置映射直接判断起始点和延伸终点，完全避免了对已有子序列的遍历检查，把时间复杂度降到了线性，这是最优的（因为至少要遍历数组一次）。

内容的提问来源于stack exchange，提问作者Sam