为何两种循环结果不同？如何优化盛最多水容器问题时间复杂度？

一、结果差异的核心原因 #

你的嵌套循环和列表推导式计算逻辑完全不一致，问题出在括号的优先级上：

• 嵌套循环的正确逻辑是：先取两个高度的较小值，再乘以两线的水平距离，公式为 min(height[i], height[j]) * abs(j - i)。
• 列表推导式里错误地写成了 min(height[i], height[j] * abs(j - i))——先计算了height[j]与水平距离的乘积，再和height[i]取最小值，完全偏离了储水量的计算规则。

拿示例数组验证：当i=1（对应高度8）、j=8（对应高度7）时，正确计算是min(8,7)*7=49，但错误的列表推导式会计算min(8,7*7)=min(8,49)=8，这就是最终结果为8的直接原因。

修正后的列表推导式应该是：

mxm = [min(height[i], height[j]) * abs(j - i) for i in range(len(height)) for j in range(len(height))]
maxim = max(mxm)

不过即使修正，该写法的时间复杂度依然是O(n²)，大数组下还是会很慢。

二、O(n)时间复杂度的优化解法 #

用双指针法可以将时间复杂度降到线性级别，思路如下：

1. 初始化左指针在数组开头（left=0），右指针在数组末尾（right=len(height)-1）；
2. 计算当前指针组合的储水量：min(height[left], height[right]) * (right - left)；
3. 移动高度较小的指针：因为储水量由较矮的边决定，移动高边无法提升储水量，移动矮边才有可能找到更高的边，从而获得更大的储水量；
4. 重复步骤2-3，直到左右指针相遇，记录过程中的最大储水量。

代码实现：

def maxArea(height):
    max_water = 0
    left = 0
    right = len(height) - 1
    while left < right:
        current_water = min(height[left], height[right]) * (right - left)
        if current_water > max_water:
            max_water = current_water
        # 移动较矮的指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

测试示例数组[1,8,6,2,5,4,8,3,7]，会返回正确结果49，且大数组下的执行效率远高于嵌套循环写法。

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