如何查找数组中中间元素小于两端最小值的数对并优化O(n²)算法

优化思路 #

你需要查找的「两元素中间所有元素都小于两者较小值」的数对，本质是经典的可见元素对问题，可以用单调递减栈实现O(n)时间复杂度求解，远优于原O(n²)的暴力方案，空间复杂度为O(n)，在数组长度较大时性能提升非常明显。

算法原理 #

维护一个栈底到栈顶严格单调递减的栈，栈中存储(元素值, 连续出现次数)的元组：

1. 遍历数组每个元素：
   • 若当前元素大于栈顶元素，说明栈顶元素找到了右侧第一个比它大的元素，弹出栈顶元素：
     • 每弹出计数为k的元素，新增k个数对：为弹出元素和当前元素组成的合法数对
     • 弹出后栈不为空时，额外新增k个数对：为弹出元素和当前新栈顶元素组成的合法数对
   • 若当前元素等于栈顶元素，直接将栈顶元素的计数+1即可
   • 若当前元素小于栈顶元素，直接将(当前元素, 1)压入栈
2. 遍历完成后处理栈中剩余元素：
   • 依次弹出栈中元素，每弹出计数为k的元素，先加k*(k-1)//2个相同元素内部组成的合法数对
   • 弹出后栈长度≥2时，再加k个数对：为弹出元素和当前栈顶元素组成的合法数对

优化后实现代码 #

def findPairs(n, values):
    if n < 2:
        return 0, []
    stack = []
    res = []

    def add_pairs(a, b, cnt=1):
        for _ in range(cnt):
            res.append((a, b))

    for val in values:
        while stack and stack[-1][0] < val:
            pop_val, pop_cnt = stack.pop()
            add_pairs(pop_val, val, pop_cnt)
            if stack:
                add_pairs(stack[-1][0], pop_val, pop_cnt)
        if stack and stack[-1][0] == val:
            stack[-1] = (val, stack[-1][1] + 1)
        else:
            stack.append((val, 1))

    while stack:
        pop_val, pop_cnt = stack.pop()
        if pop_cnt > 1:
            for i in range(pop_cnt):
                for j in range(i+1, pop_cnt):
                    res.append((pop_val, pop_val))
        if stack:
            add_pairs(stack[-1][0], pop_val, pop_cnt)

    return len(res), res

效果验证 #

用你给出的示例输入测试：
输入：n=5, values = [10,4,6,8,7]
输出数对为：[(4, 6), (10, 4), (6, 8), (10, 6), (8, 7), (10, 8)]，和示例给出的合法数对完全匹配，仅输出顺序不同，如果需要按原数组位置排序，只需要在返回前对res做一次排序即可，不影响整体时间复杂度。

额外提示：你原来的暴力实现存在边界bug，currMax初始化为0，当数组元素全为负数时会得到错误结果，优化后的代码不存在该问题。

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