基于分治法判断无重复整数列表中是否存在Small-Big-Medium子序列

我来分享下用分治法解决这个问题的具体思路，严格遵循分治「分-治-合」的核心逻辑，一步步拆解问题：

核心思路 #

我们把给定的无重复整数列表拆分为左右两个子数组，分别递归检查子数组中是否存在符合要求的三元组；如果子数组里找不到，再专门检查跨左右两个子数组的三元组情况。只要任意一种情况找到符合条件的组合，就返回「是」，否则返回「否」。

具体实现步骤 #

1. 递归终止条件

当数组长度小于3时，根本凑不出三个元素，直接返回「否」。

2. 分治处理子数组

• 先找数组的中间索引mid，把数组拆成左半部分left = L[0..mid]和右半部分right = L[mid+1..n-1]
• 先递归检查左半部分，如果左半已经找到符合条件的三元组，直接返回结果，不用再往下走了
• 再递归检查右半部分，同理，如果右半找到，直接返回「是」

3. 合并阶段：检查跨区间的三元组

如果左右子数组都没找到，那就要重点排查跨区间的情况了，这里分两种场景：

场景A：「3」（也就是三元组里最大的那个数，对应xᵢ₂）在左半部分

这种情况是说，存在i₁ < i₂ ≤ mid < i₃，满足x[i₁] < x[i₃] < x[i₂]。处理起来很简单：

• 先给左半部分算一个前缀最小值数组min_prefix：min_prefix[i]是左半部分从开头到第i个位置的最小数，这样我们就能快速知道每个i₂左边有没有比它小的数
• 把右半部分排个序，得到sorted_right，这样后面找数可以用二分查找，效率更高
• 遍历左半部分的每个元素x[i₂]：
  • 如果min_prefix[i₂] < x[i₂]（说明左边确实有更小的数x[i₁]）
  • 用二分查找在sorted_right里找有没有数c满足min_prefix[i₂] < c < x[i₂]
  • 要是找到这样的c，那(i₁, i₂, i₃)就符合要求了，直接返回「是」

场景B：「3」在右半部分

这种情况是i₁ ≤ mid < i₂ < i₃，满足x[i₁] < x[i₃] < x[i₂]。处理步骤：

• 先算出左半部分的最小值min_left，只要右半部分有比min_left大的数，左半肯定存在对应的x[i₁]
• 从右往左遍历右半部分，同时维护一个current_min（记录遍历过的元素里的最小值）：
  • 当遇到x[i₂] > current_min，而且current_min > min_left的时候，说明i₂右边有个i₃，x[i₃] = current_min，而且左半有x[i₁] < current_min
  • 这时候i₁, i₂, i₃就构成了符合条件的三元组，直接返回「是」
  • 别忘了每次遍历都更新current_min，取当前值和x[i₂]里更小的那个

4. 最终结果

要是所有情况都检查完了还是没找到，那就返回「否」。

时间复杂度说明 #

假设数组长度是n：

• 递归拆分一共是O(logn)层
• 每层合并阶段，场景A的排序+二分是O(nlogn)，场景B是O(n)
• 总体时间复杂度是O(n(logn)²)，虽然比不上单调栈的O(n)，但完全符合题目要求的分治法策略。

内容的提问来源于stack exchange，提问作者Álvaro G. Tenorio