求高效查找特定三元子序列的算法：首小、次大、末在区间内

我们需要寻找的是长度为3的子序列 (a, b, c)，满足：

• 顺序要求：a在b前，b在c前（保持原列表的相对顺序）
• 数值要求：a是三个元素中的最小值，b是最大值，且c的数值介于a和b之间（即 a < c < b）

问题分析 #

之前追踪全局最值的方法会出错，核心原因是没有严格保证a在b之前的顺序约束，导致出现a位于b之后的错误匹配。下面提供两种高效的可行方案：

方案一：预处理左最小值 + 右侧有序集合（O(n log n) 时间） #

思路 #

1. 预处理左最小值数组：先遍历一次列表，生成left_min数组，其中left_min[i]表示第i个元素左侧所有元素的最小值。这样能快速确认每个元素作为b时，左侧是否存在符合要求的a（即left_min[i] < nums[i]）。
2. 从右往左遍历维护有序集合：用有序集合存储当前元素右侧的所有元素，对每个b，只需在有序集合中查找是否存在c满足left_min[i] < c < nums[i]，利用二分查找可快速完成判断。

伪代码实现 #

def find_valid_triple(nums):
    n = len(nums)
    if n < 3:
        return None
    
    # 预处理左侧最小值数组
    left_min = [float('inf')] * n
    current_min = nums[0]
    for i in range(1, n):
        left_min[i] = current_min
        if nums[i] < current_min:
            current_min = nums[i]
    
    # 用bisect维护右侧有序元素集合
    import bisect
    right_elements = []
    for i in range(n-1, -1, -1):
        b = nums[i]
        a_candidate = left_min[i]
        if a_candidate < b:
            # 查找第一个大于a_candidate的元素位置
            idx = bisect.bisect_right(right_elements, a_candidate)
            if idx < len(right_elements) and right_elements[idx] < b:
                return (a_candidate, b, right_elements[idx])
        # 将当前元素加入有序集合
        bisect.insort(right_elements, b)
    
    return None

正确性说明 #

对于每个b，a_candidate是其左侧的最小值，严格保证a在b之前；c来自b右侧的元素，严格保证b在c之前，完全符合子序列的顺序要求。比如在错误案例[5,8,10,2,4]中，该方法会正确判断不存在符合条件的三元组。

方案二：栈维护候选对（O(n) 时间，仅判断存在性） #

如果只需要确认是否存在这样的三元组，无需返回具体值，可以用更高效的栈方法：

思路 #

维护一个栈，栈中存储(b, min_a_before_b)的二元组，其中min_a_before_b是b左侧的最小值。遍历每个元素时：

1. 检查栈顶元素，若当前元素c满足min_a_before_b < c < b，则直接返回存在；
2. 若当前元素大于栈顶的b，则弹出栈顶（后续元素若要匹配，更大的b更有优势）；
3. 将当前元素作为新的b，结合当前全局最小值压入栈；
4. 同步更新全局最小值。

伪代码实现 #

def has_valid_triple(nums):
    n = len(nums)
    if n < 3:
        return False
    
    stack = []
    current_min = nums[0]
    
    for num in nums[1:]:
        # 检查是否存在符合条件的三元组
        while stack and num < stack[-1][0]:
            if num > stack[-1][1]:
                return True
            stack.pop()
        
        # 将当前元素作为候选b压入栈
        if not stack or num > stack[-1][0]:
            stack.append( (num, current_min) )
        
        # 更新全局最小值
        if num < current_min:
            current_min = num
    
    return False

这个方法时间复杂度为O(n)，每个元素最多入栈和出栈一次，效率极高。

内容的提问来源于stack exchange，提问作者Javier Pérez Vargas