如何高效求解数组元素对的最小值与距离的最大乘积？

原解法的问题 #

你给出的暴力解法采用两层嵌套循环，时间复杂度为O(n²)。当数组长度n较大时（比如n=10^{4），总运算量会达到10}8次，运行效率急剧下降，无法处理大规模数据。

优化思路：双指针法（时间复杂度O(n)） #

这是经典的「盛最多水的容器」问题，核心思路是用双指针从数组两端向中间逼近，每次移动数值较小的指针，具体逻辑如下：

• 初始化左指针left在数组起始位置（索引0），右指针right在数组末尾位置（索引len(a)-1）
• 计算当前指针对的乘积：min(a[left], a[right]) * (right - left)，并更新结果最大值
• 比较左右指针指向的元素：如果a[left] < a[right]，则移动左指针（left +=1）；否则移动右指针（right -=1）
• 重复上述步骤，直到left >= right终止循环

为什么这样移动指针？

当前的乘积由较小的元素值和两指针间距共同决定：

• 如果移动数值较大的指针，间距会减小，但新的最小元素值不会超过原来的较小值，因此乘积只会更小，不可能得到更优解
• 如果移动数值较小的指针，虽然间距减小，但有可能遇到更大的元素，使得新的最小元素值变大，从而得到更大的乘积

优化后的代码实现 #

a = [2,5,2,2,1,5,2]
max_result = 0
left = 0
right = len(a) - 1

while left < right:
    current_val = min(a[left], a[right]) * (right - left)
    if current_val > max_result:
        max_result = current_val
    # 移动较小元素的指针
    if a[left] < a[right]:
        left += 1
    else:
        right -= 1

print(max_result)  # 输出：20

验证示例2 #

对于输入[1,2]，运行代码后会得到结果1，与预期一致。

正确性说明 #

该方法不会遗漏最优解：假设最优配对是(i,j)，当指针移动到i或j时，另一个指针会逐步向其逼近——因为在这之前的指针移动都是因为遇到了更小的元素，不会跳过这个最优配对的位置。

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