1. 问题背景与核心需求
这个问题源自经典的算法题库,属于数组与双指针技巧结合的典型应用场景。题目描述为:给定一个长度为n的非负整数数组height,每个元素代表垂直线的长度。找出两条线与x轴共同构成的容器可以容纳最多的水量。
实际工程中,这类问题可以类比于:
- 城市规划中水库容量计算
- 物流仓储中的货架空间优化
- 图形界面设计中的自适应布局
关键理解:容器的水量由两个因素决定——容器宽度(两指针间距)和容器高度(两指针中的较小值)
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法思路解析
2.1 暴力解法及其缺陷
最直观的解法是双重循环遍历所有可能的组合:
python复制max_area = 0
for i in range(len(height)):
for j in range(i+1, len(height)):
area = (j - i) * min(height[i], height[j])
max_area = max(max_area, area)
return max_area
时间复杂度O(n²),在数据量较大时(如n>10⁴)性能急剧下降。
2.2 双指针优化原理
双指针法的核心观察点:
- 初始状态:左指针在数组头(0),右指针在数组尾(n-1)
- 移动策略:每次移动高度较小的指针(因为容器的瓶颈在于较小的高度)
- 终止条件:左右指针相遇
数学证明:
- 设当前左右指针分别为i,j,对应高度h[i] ≤ h[j]
- 若移动较高指针j→j-1,新面积只可能更小(宽度减小且高度不超过h[i])
- 因此必须移动较低指针i→i+1才可能获得更大面积
3. 标准实现与优化
3.1 基础双指针实现
python复制def maxArea(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
current_area = (right - left) * min(height[left], height[right])
max_area = max(max_area, current_area)
