LeetCode 每日一题 #11：盛最多水的容器｜Python

几年前我准备求职时，也曾一头扎进 LeetCode 的题海。从最初的“看题懵圈”到后来能在面试中从容写出最优解，每天坚持刷一道题成了我提升算法能力最有效的方式。那段经历不仅帮我顺利拿到心仪 offer，更让我养成了系统思考和高效编码的习惯。

如今工作稳定了，终于有时间把当年的刷题笔记重新整理、优化，并用 Python 语言 逐题讲解清楚。希望能帮助正在准备面试、转行或想夯实基础的你——少走弯路，高效进步。

关键词：双指针、贪心算法、数学证明、面积最大化 难度：中等 推荐指数：⭐⭐⭐⭐⭐（高频面试题，双指针经典范例）

题目描述

给定一个长度为 n 的整数数组 height，其中每个元素代表坐标系中一个垂直线段的高度。 在坐标 (i, 0) 到 (i, height[i]) 画一条竖直线。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以存储的最大水量。

说明：你不能倾斜容器。

示例

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

输入: height = [1,1]
输出: 1

输入: height = [4,3,2,1,4]
输出: 16

约束条件

• n == height.length
• 2 <= n <= 10⁵
• 0 <= height[i] <= 10⁴

解题思路

容器的面积由两个因素决定：

• 宽度：两根柱子之间的距离 j – i
• 高度：较矮柱子的高度 min(height[i], height[j])

因此，面积公式为：

Area

=

(

j

−

i

)

×

min

⁡

(

height

[

i

]

,

height

[

j

]

)

\\text{Area} = (j – i) \\times \\min(\\text{height}[i], \\text{height}[j])

Area=(j−i)×min(height[i],height[j])

暴力解法（O(n²)，不推荐）

枚举所有 (i, j) 组合，计算面积取最大值。 对于 n = 10⁵，会超时。

最优解法：双指针 + 贪心策略（O(n)）

核心思想：

• 初始化左右指针 left = 0, right = n – 1
• 计算当前面积，并更新最大值
• 移动较矮的那根柱子，因为：
  • 宽度在缩小（right – left 减小）
  • 若移动较高的柱子，新高度 ≤ 原较矮高度 → 面积不可能更大
  • 只有移动较矮柱子，才有可能找到更高的柱子，从而补偿宽度损失

关键洞察： “短板效应”决定了面积上限。要突破当前面积，必须尝试替换短板。

正确性简要证明（面试加分项）：

假设 height[left] < height[right]，当前面积为 S = (right – left) * height[left]。

若固定 left，向左移动 right：

• 宽度减小
• 高度 ≤ height[left]（因 height[left] 是短板） → 所有可能的新面积都 ≤ S

因此，left 与任何 right' < right 的组合都不可能优于当前 S，可安全舍弃 left。

同理，若 height[right] 更矮，则舍弃 right。

Python 代码实现

双指针法（唯一高效解法）

class Solution:
def maxArea(self, height: List[int]) –> int:
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)
• 逻辑简洁，易于手写

细节注意：

• 使用 min() 获取有效高度
• 比较后直接移动指针，无需额外判断相等情况（相等时移动任意一端均可）

复杂度分析

对比暴力法 O(n²)，效率提升显著

小结 & 面试技巧

• 核心思想：贪心 + 双指针，通过“移动短板”逐步逼近最优解
• 必讲亮点：正确性证明（为什么移动短板不会错过最优解）
• 常见误区：
  • 尝试移动高板（逻辑错误）
  • 在相等时只移动一侧（其实任意移动都正确，但需保持一致性）
  • 忘记更新 max_area
• 面试话术：

  “我使用双指针从两端向中间收缩。每次计算面积后，移动较矮的柱子，因为只有这样才可能获得更大的面积。这个策略的正确性可以通过反证法证明：固定短板时，其他组合不可能更优。”

• 扩展思考：
  • 如果允许移除 k 根柱子后再选两根，如何求最大面积？（变种题）
  • 能否推广到三维“盛水”问题？（如接雨水 II）

下期预告

明天我们将挑战第 12 题：整数转罗马数字，带你用贪心策略轻松搞定数字映射！

坚持每天一道 LeetCode，用 Python 写出优雅代码，夯实算法基础，拿下心仪 Offer！ 关注专栏，不错过每日更新！