当前位置：首页 > news >正文

LeetCode 热题 100 11. 盛最多水的容器

news 来源：原创 2025/9/17 8:48:28

LeetCode 热题 100 | 11. 盛最多水的容器

大家好，今天我们来解决一道经典的算法题——盛最多水的容器。这道题在LeetCode上被标记为中等难度，要求我们找到两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水。下面我将详细讲解解题思路，并附上Python代码实现。

问题描述

给定一个长度为 n 的整数数组 height，其中 height[i] 表示第 i 条垂线的高度。你需要找到两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

注意：你不能倾斜容器。

示例：

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

解题思路

核心思想

双指针法：
- 使用两个指针 left 和 right，分别指向数组的起始和末尾。
- 计算当前两个指针所指向的垂线构成的容器的面积，并记录下最大的面积。
- 移动指针的规则是：移动指向较短垂线的指针，因为只有移动较短的垂线，才有可能在后续的步骤中找到更大的面积。
面积计算：
- 容器的面积由两个指针所指向的垂线中较短的那条决定，宽度为两个指针之间的距离。

Python代码实现

def maxArea(height):left, right = 0, len(height) - 1  # 初始化双指针max_area = 0  # 记录最大面积while left < right:# 计算当前容器的面积current_area = min(height[left], height[right]) * (right - left)# 更新最大面积max_area = max(max_area, current_area)# 移动指针if height[left] < height[right]:left += 1else:right -= 1return max_area# 测试示例
print(maxArea([1,8,6,2,5,4,8,3,7]))  # 输出: 49
print(maxArea([1,1]))  # 输出: 1

代码解析

初始化指针：
- left 指向数组的起始位置，right 指向数组的末尾位置。
计算面积：
- 当前容器的面积由两个指针所指向的垂线中较短的那条决定，宽度为两个指针之间的距离。
更新最大面积：
- 每次计算完当前面积后，与之前的最大面积进行比较，更新最大面积。
移动指针：
- 根据当前两个指针所指向的垂线的高度，移动较短的垂线的指针，以期望在后续的步骤中找到更大的面积。
返回结果：
- 最终返回记录的最大面积。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组。
空间复杂度：O(1)，只使用了常数个额外空间。

示例运行

示例1

输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49

示例2

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

进阶：优化思路

在基本解法中，我们每次都会计算当前容器的面积并更新最大面积。如果数组中的垂线高度分布较为均匀，这种方法已经非常高效。但如果数组中有很多相同高度的垂线，可以进一步优化指针的移动策略，减少不必要的计算。

总结

通过使用双指针法，我们可以高效地找到能够容纳最多水的容器。这种方法不仅简洁，而且效率非常高，适合处理类似的问题。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！