盛最多雨水----双指针

题目

给定一个height长度为n的整数数组n。绘制了一些垂直线，使得线n的两个端点分别为x和y 。ith(i, 0)(i, height[i])

找到两条直线，使它们与 x 轴一起构成一个容器，使得该容器中容纳的水最多。

恢复容器所能储存的最大水量。

请注意，容器不能倾斜。

核心思路

1. 为什么用双指针？

两个柱子能盛的水，取决于：

宽度 = 两柱子之间的距离
高度 = 较矮柱子的高度

面积 = 宽度 × 高度

2. 关键洞察：移动哪边？

假设在位置 left 和 right：

高度较矮的那边，决定了盛水量
移动较矮的一边，可能找到更大的面积
移动较高的一边，宽度变小，高度不变/变小，面积只会更小

例如: height[left]=1, height[right]=7

移动 left（矮边）:

• 高度可能变大 → 面积可能变大
• 宽度变小 → 但高度可能补偿

移动 right（高边）:

• 高度不会变高（还是以left为准）
• 宽度变小 → 面积一定变小

3. 算法步骤

1. left = 0, right = 最右边
2. 计算当前面积
3. 移动较矮那边的指针
4. 重复直到指针相遇

代码实现：

intmaxArea(vector<int>&height){intleft=0,right=height.size()-1;intarea=0;while(left<right){intw=right-left;inth=min(height[left],height[right]);area=max(area,w*h);if(height[left]<height[right])left++;elseright--;}returnarea;}

思考：

每次循环都执行：

1. 调用 min() 求较矮边
2. 计算 w*h
3. 调用 max() 更新面积

每次循环都做完整的面积计算（即使面积必然更小）
循环 N 次 → N 次 min() + N 次 max() + N 次乘法

因此，我们引进lmax,ramx指针
仅当「当前边超过历史最大高度」时才计算：

1. 无 min() 调用（用 lmax/rmax 替代）
2. 仅必要时计算 w*lmax/rmax + 调用 max()

代码实现：

intmaxArea(vector<int>&height){intleft=0,right=height.size()-1;intarea=0,lmax=-1,rmax=-1;while(left<right){intw=right-left;if(height[left]<height[right]){if(height[left]>lmax){lmax=height[left];area=max(w*lmax,area);}left++;}else{if(height[right]>rmax){rmax=height[right];area=max(w*rmax,area);}right--;}}returnarea;}

对比经典解法：
跳过所有「不可能更大」的面积计算（仅更新历史最大时才计算）
循环 N 次 → 0 次 min() + M 次 max() + M 次乘法（M < N，M 是历史最大更新次数）

逐步演示

初始化

left = 0, right = 8
lmax = -1, rmax = -1, area = 0

第1轮

比较: height[0]=1 < height[8]=7 → 处理左边

判断: height[0]=1 > lmax(-1) → 更新 lmax = 1

面积 = 宽度(8) × lmax(1) = 8
area = max(0, 8) = 8

移动: left++ → left = 1

第2轮

比较: height[1]=8 > height[8]=7 → 处理右边

判断: height[8]=7 > rmax(-1) → 更新 rmax = 7

面积 = 宽度(7) × rmax(7) = 49
area = max(8, 49) = 49 ✅ 更新最大面积!

移动: right-- → right = 7

第3轮

比较: height[1]=8 > height[7]=3 → 处理右边

判断: height[7]=3 > rmax(7)? 否

面积 = 宽度(6) × rmax(7) = 42
area = max(49, 42) = 49

移动: right-- → right = 6

第4轮

比较: height[1]=8 = height[6]=8 → 处理右边(else分支)

判断: height[6]=8 > rmax(7) → 更新 rmax = 8

面积 = 宽度(5) × rmax(8) = 40
area = max(49, 40) = 49

移动: right-- → right = 5

第5轮

比较: height[1]=8 > height[5]=4 → 处理右边

判断: height[5]=4 > rmax(8)? 否

面积 = 宽度(4) × rmax(8) = 32
area = max(49, 32) = 49

移动: right-- → right = 4

第6轮

比较: height[1]=8 > height[4]=5 → 处理右边

判断: height[4]=5 > rmax(8)? 否

面积 = 宽度(3) × rmax(8) = 24
area = max(49, 24) = 49

移动: right-- → right = 3

第7轮

比较: height[1]=8 > height[3]=2 → 处理右边

判断: height[3]=2 > rmax(8)? 否

面积 = 宽度(2) × rmax(8) = 16
area = max(49, 16) = 49

移动: right-- → right = 2

第8轮

比较: height[1]=8 > height[2]=6 → 处理右边

判断: height[2]=6 > rmax(8)? 否

面积 = 宽度(1) × rmax(8) = 8
area = max(49, 8) = 49

移动: right-- → right = 1