盛最多水的容器：双指针法的经典应用

如何用最少的线条，围出最大的面积？这不仅是一道算法题，更是一个充满智慧的思考题。

问题引入

想象一下，我们有一排高低不一的木板，现在要用其中两块木板作为容器的两侧，其他木板全部忽略，问这个容器最多能盛多少水？

这就是 LeetCode 上经典的第11题“盛最多水的容器”所描述的场景。这个问题不仅在技术面试中经常出现，其背后的解法思路也体现了算法设计的精妙之处。

问题定义

给定一个长度为 n的非负整数数组 height，其中 height[i]表示第 i条垂直线的高度。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

注意：你不能倾斜容器，且 n 的值至少为 2。

示例：

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

暴力解法：一个直观但低效的起点

首先，我们可能会想到最简单的解法——尝试所有可能的组合：

def maxArea_bruteforce(height):
    max_area = 0
    n = len(height)
    
    for i in range(n):
        for j in range(i + 1, n):
            # 宽度是下标差，高度是两根线中较短的那根
            width = j - i
            h = min(height[i], height[j])
            area = width * h
            max_area = max(max_area, area)
    
    return max_area

这个解法的时间复杂度是 O(n²)，在数组较大时会非常慢。我们需要一个更高效的解法。

优化思路：双指针法

仔细观察这个问题，我们会发现一个关键特性：容器的容量由较短的边决定。

让我们思考一下：

初始时，我们让两个指针分别指向数组的两端，这样宽度最大
然后，我们逐步向内移动指针
移动的策略是：总是移动较短的那条边对应的指针

为什么这个策略是正确的？

因为容器的容量由两个因素决定：宽度和较短板的高度。当我们向内移动指针时，宽度一定会减小。为了有可能获得更大的面积，我们必须希望高度增加。而移动较短的边，才有可能让高度增加（移动较长的边，高度最多保持不变，甚至可能变小，而宽度又减小了，所以面积一定不会变大）。

高效解法：双指针法实现

def maxArea(height):
    # 初始化双指针
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        # 计算当前面积
        width = right - left
        h = min(height[left], height[right])
        current_area = width * h
        
        # 更新最大面积
        max_area = max(max_area, current_area)
        
        # 移动较短的边
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

算法分析

时间复杂度：O(n)

我们只遍历了数组一次，每个元素最多被访问一次。

空间复杂度：O(1)

只使用了常数级别的额外空间。

示例推演

让我们用示例数组 [1,8,6,2,5,4,8,3,7]来验证一下算法：

初始：left=0(高度1), right=8(高度7)，面积=min(1,7)*8=8
移动左指针：left=1(高度8), right=8(高度7)，面积=min(8,7)*7=49
移动右指针：left=1(高度8), right=7(高度3)，面积=min(8,3)*6=18
…继续移动，最终得到最大面积49

边界情况处理

我们的算法已经自然地处理了各种边界情况：

数组长度为2：直接计算两个元素构成的面积
有零高度：零高度的边不会影响移动策略
所有高度相等：无论怎么移动，面积都会递减，但仍能正确返回最大面积

变体与扩展

这个问题的解法可以扩展到类似的问题上，比如：

接雨水问题：同样是计算面积，但需要考虑中间的所有条形
最大矩形面积：在柱状图中找最大矩形
两数之和：虽然问题不同，但双指针的思想是相通的

总结

“盛最多水的容器”这个问题展示了如何通过观察问题特性，设计出高效的解法。双指针法在这里的巧妙应用告诉我们：

有时候，从两端向中间靠拢比从一端开始遍历更高效
决策的局部最优性：每次移动较短的边，这个局部最优选择能保证全局最优
时间复杂度的大幅优化：从O(n²)到O(n)的飞跃

这种解法不仅优雅，而且高效，体现了算法设计的艺术。在实际开发中，这种思维方式也能帮助我们解决许多看似复杂的问题。

动手练习

理解了算法之后，不妨尝试一下LeetCode上的原题，或者思考以下变体：

如果容器可以倾斜，解法会有什么变化？
如果有三条边可以组成容器，如何找到最大容量？