LeetCode 11 盛最多水的容器：从暴力枚举到双指针优化

最近刷到 LeetCode 11《盛最多水的容器》，这道题是双指针算法的经典入门题。刚开始看到题目时，我的第一反应是暴力枚举所有可能的柱子组合，但仔细分析后会发现，这种做法效率太低，而双指针才是这道题真正的核心。

题目描述

给定一个数组 height，数组中的每个元素表示一根柱子的高度。

从中选择两根柱子，与 x 轴组成一个容器，求能够容纳的最大水量。

例如：

height = [1,8,6,2,5,4,8,3,7]

最终答案为：

49

对应的是高度为 8 和 7 的两根柱子。

---

容器面积怎么计算？

很多同学第一次做这道题时容易忽略一点：

容器高度并不是由高的柱子决定，而是由较矮的柱子决定。

因为水位超过矮柱子时就会流出去。

所以面积计算公式为：

面积 = 宽度 × 较矮柱子的高度

其中：

宽度 = 两根柱子的距离
高度 = min(左柱子高度, 右柱子高度)

例如：

height = [1,8,6,2,5,4,8,3,7]

选择：

8 和 7

对应下标：

1 和 8

则：

宽度 = 8 - 1 = 7
高度 = min(8,7) = 7
面积 = 7 × 7 = 49

---

最容易想到的方法：暴力枚举

最直接的思路是：

固定左边柱子，然后让右边柱子遍历后面的所有位置。

把所有组合都计算一遍。

例如：

for i in range(len(height)):
    for j in range(i + 1, len(height)):
        area = (j - i) * min(height[i], height[j])

完整代码：

class Solution:
    def maxArea(self, height):
        max_area = 0

        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                width = j - i
                h = min(height[i], height[j])
                area = width * h

                if area > max_area:
                    max_area = area

        return max_area

时间复杂度

O(n²)

因为：

• 第一层循环 n 次
• 第二层循环最多 n 次

总共需要计算：

n × n

级别的数据。

当数组很长时，LeetCode 会直接超时。

---

双指针优化

既然暴力法要枚举所有组合，那有没有办法减少无意义的计算？

答案就是双指针。

初始化

让两个指针分别放在数组两端：

left = 0
right = len(height) - 1

此时宽度最大。

---

关键问题：为什么移动矮的柱子？

这是整道题最重要的地方。

假设当前：

左高 = 3
右高 = 8

容器高度：

min(3,8)=3

面积：

宽度 × 3

如果移动右边（高柱子）：

宽度变小
高度仍然最多是3

面积一定不会变大。

因为决定水位的是左边那根高度为3的柱子。

---

而如果移动左边（矮柱子）：

宽度虽然变小
但新的柱子可能更高

例如：

3 → 7

那么容器高度就有机会提高。

面积才可能增大。

因此：

移动高柱子一定没有收益，移动矮柱子才有机会获得更大的面积。

这就是双指针成立的核心依据。

---

双指针代码

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        max_area = 0

        while left < right:

            width = right - left
            h = min(height[left], height[right])

            area = width * h

            if area > max_area:
                max_area = area

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

---

示例运行过程

输入：

[1,8,6,2,5,4,8,3,7]

第一次

left=0 (1)
right=8 (7)

宽度=8
高度=1

面积=8

更新：

max=8

左边更矮：

left++

---

第二次

left=1 (8)
right=8 (7)

宽度=7
高度=7

面积=49

更新：

max=49

右边更矮：

right--

---

第三次

left=1 (8)
right=7 (3)

面积=18

小于49。

继续移动右指针。

---

后面不断缩小区间，虽然还能算出很多面积，但都无法超过49。

最终答案：

49

---

为什么时间复杂度是 O(n)？

因为：

while left < right:

整个过程中：

• left 只会向右移动
• right 只会向左移动

每个位置最多访问一次。

因此：

时间复杂度：O(n)
空间复杂度：O(1)

相比暴力法的 O(n²)，效率提升非常明显。

---

这道题真正要掌握什么？

很多人记住了代码，却没有理解双指针思想。

实际上这道题最重要的收获是：

暴力法

枚举所有可能。

时间复杂度 O(n²)

双指针法

利用题目性质进行剪枝。

移动高柱子没有意义
移动矮柱子才有机会获得更优解

从而把：

O(n²)

优化到：

O(n)

这也是双指针算法最经典的应用场景之一。

---

总结

这道题的核心只有两句话：

1. 容器面积 = 宽度 × 两侧较矮柱子的高度；
2. 双指针每次只移动较矮的那一侧，因为移动较高的一侧不可能得到更大的面积。

理解了这两个结论，代码基本就能顺利写出来。

后面刷到三数之和、接雨水、有序数组求和等经典双指针题目时，也会不断用到类似的思想。