如何优化MaxProductOfThree算法 将时间复杂度降至O(n)

原代码问题分析 #

你原来的实现通过枚举所有三元组计算乘积取最大值，本质时间复杂度为O(N³)，当数组长度较大时运算量会指数级增长，因此性能得分为0。

优化核心思路 #

三个数的最大乘积仅存在两种可能的场景，无需遍历所有组合：

• 场景1：数组中最大的三个正数的乘积，适用于全为正数、仅存在1个负数的情况
• 场景2：数组中最小的两个负数（负负得正）乘以最大的正数，适用于存在至少2个负数，且两个最小负数的乘积大于第二、第三大正数乘积的情况

仅需要维护5个关键值即可覆盖所有场景：max1（数组最大值）、max2（第二大值）、max3（第三大值）、min1（数组最小值）、min2（第二小值），最终比较两种场景的乘积取最大值即可。

O(N)时间复杂度实现代码 #

def solution(A):
    # 初始化最大的三个值，初始设为负无穷
    max1 = max2 = max3 = float('-inf')
    # 初始化最小的两个值，初始设为正无穷
    min1 = min2 = float('inf')
    
    for num in A:
        # 更新最大的三个值
        if num > max1:
            max3 = max2
            max2 = max1
            max1 = num
        elif num > max2:
            max3 = max2
            max2 = num
        elif num > max3:
            max3 = num
        
        # 更新最小的两个值
        if num < min1:
            min2 = min1
            min1 = num
        elif num < min2:
            min2 = num
    
    # 计算两种可能的最大乘积，取较大值
    return max(max1 * max2 * max3, min1 * min2 * max1)

逻辑说明 #

• 一次遍历数组即可完成5个关键值的更新，时间复杂度为O(N)，空间复杂度为O(1)，远优于原实现的O(N³)
• 覆盖所有边界场景：包括数组全为负数、存在多个负数、混合正负值、数组长度刚好为3等情况，正确性可以达到100%
• 无需额外排序操作，性能可以达到满分标准

内容的提问来源于stack exchange，提问作者Berke Şentürk