为何双指针法求解数组最大(j-i)*min(a[j],a[i])问题有效？

开发者阿泽

2026-8-19

双指针解法求最大容器面积的原理解析

问题描述

给定一个数组，找出(j-i)*min(a[j],a[i])的最大值，其中i和j是数组中范围为{0,1,…,n-1}的不同索引（n为数组长度）。有人采用了双指针从数组两端出发，每次舍弃值较小的一端的解法，且该解法能正确运行，现解析其原理。

解法代码

i, j = 0, n-1
ansSoFar = 0
while i <= j:
    ansSoFar = max(ansSoFar, (j-i)*min(A[i], A[j]))
    if A[i] > A[j]:
        j -= 1
    else:
        i += 1
return ansSoFar

原理解析

这个解法的核心是贪心策略，关键在于理解「舍弃较小端为什么不会错过最优解」：

假设当前左指针i对应的值是A[i]，右指针j对应的值是A[j]，且A[i] < A[j]。此时计算的面积为(j-i)*A[i]。
如果此时移动右指针到j-1，新的面积是(j-1-i)*min(A[i], A[j-1])。不管A[j-1]比A[i]大还是小，这个新面积的宽度比原来少1，而高度最多等于A[i]（因为A[i]是原来的较小值），所以新面积肯定小于等于原来的(j-i)*A[i]，不可能成为最优解。
反过来，如果移动左指针到i+1，虽然宽度减少了1，但有可能遇到更大的A[i+1]，从而得到更大的面积。
同理，当A[j] < A[i]时，所有以j为右端点、i' > i的组合，都不可能比当前的(j-i)*A[j]更大，所以可以直接舍弃j这个右端点，移动右指针。
这种逐步缩小范围的方式，会遍历所有可能的「潜在最优解」，不会漏掉真正的最大值。