数组峰值订单ID处理序列问题：能否实现O(n)复杂度解法？

AI 小北

2026-7-7

存在O(n)时间复杂度的解决方案

要实现O(n)复杂度，关键在于避免每次遍历数组找最小峰值，而是通过双向链表维护元素的邻居关系，结合桶排序（计数排序）快速定位当前最小的峰值元素，同时处理元素移除后相邻节点的峰值状态变化，每个元素仅被处理一次。

预处理双向链表与初始峰值
- 用两个数组prev和next模拟双向链表，分别记录每个索引的前一个和后一个元素索引（比如prev[i]是i的左邻居索引，next[i]是右邻居索引），O(n)时间完成初始化。
- 遍历数组一次，标记所有初始峰值：
  - 首元素：若arr[0] > arr[1]，标记为峰值。
  - 尾元素：若arr[-1] > arr[-2]，标记为峰值。
  - 中间元素：若arr[i] > arr[prev[i]]且arr[i] > arr[next[i]]，标记为峰值。
- 同时，用桶（数组）按元素值分类存储所有峰值的索引，桶的大小由数组中元素的最大值决定，O(n)时间完成。
按从小到大处理峰值
- 从最小的桶开始遍历，依次处理每个桶中的峰值索引：
  - 若当前元素已被移除，跳过。
  - 将该元素加入结果序列，标记为已移除。
  - 获取其左邻居l和右邻居r，更新双向链表：next[l] = r，prev[r] = l。
  - 检查左邻居l是否成为新峰值：
    - 如果l不是首元素（prev[l] != -1），需要满足arr[l] > arr[prev[l]]且arr[l] > arr[r]；如果是首元素，只需arr[l] > arr[r]。
    - 若满足且之前不是峰值，标记为峰值并加入对应桶中。
  - 同理检查右邻居r是否成为新峰值，满足则加入对应桶中。
完成处理
- 当所有桶遍历完成，结果序列即为所求的订单处理序列。

预处理阶段：O(n)时间遍历数组构建链表和初始峰值，桶的初始化和填充也是O(n)。
处理阶段：每个元素最多被加入桶一次，最多被处理一次，每个邻居检查操作是O(1)，整体时间复杂度为O(n + K)，其中K是元素值的范围。若K与n同阶（比如元素值在0~n-1范围内），则整体复杂度为O(n)。

以初始数组[3,1,5,4,2]为例：

初始峰值是3（首元素>右）和5（中间元素>左右），对应桶中3的桶存索引0，5的桶存索引2。
先处理最小的峰值3，加入序列，移除后数组变为[1,5,4,2]，更新链表后检查1的状态（1的右邻居是5，1<5，不是峰值）。
接着处理峰值5，加入序列，移除后数组变为[1,4,2]，检查1（右邻居是4，1<4）和2（左邻居是4，2<4），都不是峰值；但4此时是中间元素，1<4>2，成为新峰值，加入4的桶。
处理4，加入序列，移除后数组变为[1,2]，检查2（左邻居是1，2>1，成为峰值），加入2的桶。
处理2，加入序列，最后处理1，得到序列[3,5,4,2,1]，与示例一致。

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