LeetCode 42. 接雨水 算法题解
一、题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
核心规则：某一根柱子上方能接住的雨水量，由该柱子左侧最高柱子和右侧最高柱子中的较小值，减去当前柱子高度决定。若当前柱子高度高于两侧极值，则无法接水。
公式：当前柱子接水量 = min(左侧最大高度, 右侧最大高度) - 当前柱子高度（结果小于0时取0）
二、解题思路（双指针最优解法）
1. 暴力思路缺陷
最直观的暴力解法是遍历每一根柱子，分别向左、向右遍历找到最大高度，计算单柱接水量后累加。但该方法时间复杂度为 O(n²)，数据量大时会超时，效率极低。
2. 双指针优化核心思想
采用左右双指针一次遍历数组，时间复杂度优化至 O(n)，空间复杂度 O(1)，是该题最优解法。核心逻辑如下：
- 定义左指针
left从数组头部出发，右指针right从数组尾部出发； - 维护两个变量
leftMAX（左指针遍历过的区域最大高度）、rightMAX（右指针遍历过的区域最大高度）； - 关键结论：若
leftMAX < rightMAX，当前左指针位置的接水量仅由leftMAX决定。因为右侧一定存在更大的高度屏障，无需寻找全局右侧最大值；反之则由rightMAX决定右指针位置接水量。 - 每次计算当前指针位置接水量，累加结果，然后移动对应指针，直至双指针重合，遍历结束。
三、完整AC代码（C++）
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
// 数组为空时直接返回0，无柱子无法接水
if(n == 0) return 0;
// 定义左右指针、左右区域最大高度、接水总量
int left = 0,right = n-1;
int leftMAX = 0,rightMAX = 0;
int ras = 0;
// 双指针遍历，指针重合时遍历完成
while(left < right){
// 更新当前左右区域的最大高度
leftMAX = max(leftMAX,height[left]);
rightMAX = max(rightMAX,height[right]);
// 左侧最大高度更小，由左侧屏障决定接水量
if(leftMAX < rightMAX){
ras += leftMAX - height[left];
left++;
}else{
// 右侧最大高度更小，由右侧屏障决定接水量
ras += rightMAX - height[right];
right--;
}
}
return ras;
}
};
四、代码逐行详细解读
-
数组判空处理：获取数组长度
n，若数组为空，直接返回接水量 0，避免后续遍历报错。 -
变量初始化：
left = 0, right = n-1：左右指针分别指向数组首尾；leftMAX、rightMAX：记录左右遍历区间的最大柱子高度，初始为0；ras：累加存储总接水量，初始为0。
-
双指针循环遍历：循环条件
left < right，保证所有柱子遍历完成，不重复计算。 -
更新区间最大高度：每次循环先更新当前左右指针位置的区间最大值，确保最大值是已遍历区域的最高柱子。
-
判断屏障、计算接水量：
- 当
leftMAX < rightMAX：左指针位置的积水高度受左侧矮屏障限制，计算当前柱子积水并累加，左指针右移； - 否则：右指针位置的积水高度受右侧矮屏障限制，计算当前柱子积水并累加，右指针左移。
- 当
-
返回结果：遍历结束后，
ras即为总接雨水量。
五、复杂度分析
1. 时间复杂度：O(n)
双指针仅对数组进行一次遍历，每个元素仅被访问一次，无嵌套循环，时间效率最优。
2. 空间复杂度：O(1)
全程仅使用常数个变量存储指针、最大值、结果，未开辟额外数组、栈等数据结构，原地遍历计算，空间开销极小。