本文目录
1 中文题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明：
容器不能倾斜容器
示例 1：
- 输入：
[1,8,6,2,5,4,8,3,7] - 输出：
49 - 解释：图中垂直线代表输入数组
[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49=7*7。
示例 2：
- 输入：
height = [1,1] - 输出：
1
提示：
- 2 ≤ h e i g h t . l e n g t h ≤ 1 0 5 2 \leq height.length \leq 10^5 2≤height.length≤105
- 0 ≤ h e i g h t [ i ] ≤ 1 0 4 0 \leq height[i] \leq 10^4 0≤height[i]≤104
2 求解思路
2.1 基础解法：暴力算法
思路
遍历所有可能的左右边界组合，计算每个组合形成的容器面积，并维护最大面积值。本质上是一个双重循环遍历所有可能性。
算法详细步骤：
- 初始化最大面积为0
- 外层循环遍历左边界（从第一个元素到倒数第二个）
- 内层循环遍历右边界（从左边界的下一个元素到最后一个）
- 对每对边界，计算容器面积：
- 宽度 = 右边界索引 - 左边界索引
- 高度 = min(左边界高度, 右边界高度)
- 面积 = 宽度 × 高度
- 更新最大面积
Python代码
class Solution:
def maxArea(self, height: List[int]) -> int:
"""
计算能够盛放最多水的容器面积
参数:
height: 整数数组，表示每个位置的高度
返回:
最大容器面积
示例:
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
"""
# 数组长度
n = len(height)
# 特殊情况处理：如果数组长度小于2，无法形成容器
if n < 2:
return 0
# 初始化最大面积为0
max_area = 0
# 外层循环：遍历左边界
for i in range(n):
# 内层循环：遍历右边界
for j in range(i + 1, n):
# 计算容器的宽度
width = j - i
# 计算容器的高度（两边取最小值）
container_height = min(height[i], height[j])
# 计算当前容器的面积
area = width * container_height
# 更新最大面积
max_area = max(max_area, area)
return max_area
时空复杂度分析
- 时间复杂度：O(n²)
- 外层循环：n次
- 内层循环：最多n-1次
- 空间复杂度：O(1)
该代码因为时间限制而无法通过所有测试用例
2.2 优化解法：分治法
思路
通过计算当前区间的容器面积，并根据左右高度的比较来决定收缩方向，保留较高的边界继续递归求解子区间的最大容量，最终返回当前容器面积和子问题最大面积的较大值，这样不断缩小搜索空间直到找到全局最优解。
算法详细步骤：
- 使用分治法，每次考虑当前区间[left, right]能形成的容器
- 计算当前区间的容量：宽度 * 最小高度
- 根据左右两边的高度决定下一步往哪个方向收缩：
- 如果左边较低，右移左边界
- 如果右边较低或相等，左移右边界
- 递归处理子区间，直到区间长度小于2
python代码
class Solution:
def maxArea(self, height: List[int]) -> int:
"""
使用分治法求解盛最多水的容器问题
参数:
height: 高度数组，表示每个位置的线段高度
返回:
能够盛水的最大容量
示例:
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 在下标1和8处的线段可以容纳最多的水
"""
def divide_and_conquer(left: int, right: int) -> int:
"""
递归函数，计算指定范围内的最大容量
参数:
left: 左边界索引
right: 右边界索引
返回:
当前范围内的最大容量
"""
# 基本情况：如果区间长度小于2，无法形成容器
if right - left < 1:
return 0
# 如果区间长度为2，直接计算容量
if right - left == 1:
return min(height[left], height[right]) * (right - left)
# 计算当前区间的容量
current_area = min(height[left], height[right]) * (right - left)
# 决定下一步往哪个方向收缩
if height[left] < height[right]:
# 左边较低，尝试右移左边界
next_area = divide_and_conquer(left + 1, right)
else:
# 右边较低或相等，尝试左移右边界
next_area = divide_and_conquer(left, right - 1)
# 返回当前区间容量和子区间容量的较大值
return max(current_area, next_area)
# 特殊情况处理
if len(height) < 2:
return 0
# 调用递归函数，计算整个数组范围内的最大容量
return divide_and_conquer(0, len(height) - 1)
时空复杂度分析
- 时间复杂度分析：最坏情况：O(n)，其中n是数组长度
- 每次递归都缩小区间范围，总共需要n次递归
- 空间复杂度分析：O(n)，主要是递归调用栈的开销
2.3 最优解法：双指针法
思路
使用左右指针分别指向数组两端，通过比较两个指针指向的高度来决定移动哪个指针。由于容器的面积由较短的一边决定，因此每次移动高度较小的那个指针，寻找可能的更大面积。
算法详细步骤：
- 初始化左右指针分别指向数组两端
- 当左指针小于右指针时，循环执行：
- 计算当前面积（宽度 × 最小高度）
- 更新最大面积
- 移动较小高度的指针向中间靠拢
- 返回最大面积
python代码
class Solution:
def maxArea(self, height: List[int]) -> int:
"""
使用双指针法计算能够盛放最多水的容器面积
参数:
height: 整数数组，表示每个位置的高度
返回:
最大容器面积
示例:
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
"""
# 特殊情况处理
if len(height) < 2:
return 0
# 初始化变量
max_area = 0 # 记录最大面积
left = 0 # 左指针，指向数组开始位置
right = len(height) - 1 # 右指针，指向数组结束位置
# 当左右指针未相遇时继续循环
while left < right:
# 计算当前宽度（两个指针之间的距离）
current_width = right - left
# 计算当前高度（两个指针指向的高度的最小值）
current_height = min(height[left], height[right])
# 计算当前面积
current_area = current_width * current_height
# 更新最大面积
max_area = max(max_area, current_area)
# 移动较小高度的指针
# 因为如果移动较大高度的指针，宽度减小，高度不会增加，面积一定会变小
if height[left] < height[right]:
# 左边高度小，移动左指针
left += 1
else:
# 右边高度小或相等，移动右指针
right -= 1
return max_area
时空复杂度分析
- 时间复杂度分析：O(n)
- 每次迭代必定移动一个指针，左右指针最多移动 n-1 次后相遇
- 每个元素最多被访问一次
- 空间复杂度分析：O(1)
- 两个指针变量
- 最大面积变量
- 临时计算变量
3 题目总结
题目难度：中等
数据结构：数组
应用算法：双指针、分治法