如何求解数组最大右侧特殊值？是否存在优于O(n²)的解法？

原问题是对数组每个元素A[i]，找右侧第一个比它大的元素的索引（最小j>i且A[j]>A[i]），可通过单调栈O(n)解决。现在需求改为找右侧最后一个比它大的元素的索引（最大j>i且A[j]>A[i]），问是否存在优于O(n²)的解法。

答案是肯定的，存在O(n log n)的高效解法，以下是两种具体实现思路：

解法1：线段树查询（O(n log n) 时间复杂度） #

思路 #

构建线段树维护区间最大值，通过查询指定区间内大于目标值的最右索引，快速得到每个元素的结果。核心是利用线段树的区间查询能力，优先检索右子区间以保证找到最右侧的符合条件元素。

具体步骤 #

1. 构建线段树：

   • 每个线段树节点包含区间范围[l, r]和该区间的最大值max_val。
   • 叶子节点对应数组单个元素，max_val为元素值；非叶子节点的max_val取左右子节点的最大值。

2. 查询最右符合条件的索引：
   对每个元素A[i]，查询区间[i+1, n-1]中大于A[i]的最右索引，逻辑如下：

   • 若当前节点的max_val ≤ A[i]，返回-1（该区间无符合条件元素）。
   • 若当前节点是叶子节点，返回其索引。
   • 优先查询右子区间：若右子区间存在符合条件的索引，直接返回；否则查询左子区间。

3. 遍历处理：
   遍历每个索引i，执行上述查询，将结果存入结果数组；若返回-1，说明i右侧没有比A[i]大的元素。

解法2：离线处理 + 并查集（O(n log n) 时间复杂度） #

思路 #

通过离线排序结合并查集，快速定位每个元素右侧符合条件的最大索引。核心是利用并查集记录每个位置右侧第一个未被处理的位置，确保查询到的是值更大的最右元素。

具体步骤 #

1. 预处理元素：
   将数组元素按值从小到大排序，保留原始索引，得到列表elements = [(A[i], i) for i in 0..n-1]。

2. 初始化并查集：
   定义parent数组，parent[k]表示位置k右侧第一个未被处理的位置。初始时parent[k] = k+1，parent[n] = -1（超出数组范围）。

3. 处理元素：
   按排序后的顺序遍历每个元素(A[i], i)：

   • 调用find(i+1)得到j，j即为i右侧第一个未被处理的位置（未被处理的元素值均大于A[i]）。
   • 若j != -1，res[i] = j；否则res[i] = -1。
   • 更新parent[i] = find(i+1)，标记位置i已处理，后续查询会跳过该位置。

为什么常规单调栈无法解决？ #

常规单调栈解决“右侧第一个更大元素”时，会弹出栈中小于当前元素的元素，仅保留最近的更大元素。但对于“右侧最后一个更大元素”，被弹出的较小元素可能是左侧某些元素的目标索引，单调栈无法保留这些元素的信息，因此无法直接实现O(n)解法。目前已知的最优解法时间复杂度为O(n log n)，显著优于O(n²)。

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