接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
利用双指针法高效地计算雨水蓄积量。该方法通过从数组两端向中间遍历，动态维护左右最大高度，避免了重复计算，时间复杂度为O(n)，空间复杂度为O(1)。
方法思路
- 双指针初始化：左指针
left指向数组起始位置，右指针right指向数组末尾。 - 维护左右最大高度：
leftMax记录左指针左侧的最大高度，rightMax记录右指针右侧的最大高度。 - 移动指针并计算水量：
- 当
leftMax < rightMax时，左指针处的水量由leftMax决定，计算后左指针右移。 - 否则，右指针处的水量由
rightMax决定，计算后右指针左移。
- 当
- 累加水量：每次计算当前位置的蓄水量并累加到总结果中。
代码实现
function trap(height) {
if (height.length < 3) return 0; // 至少需要3个柱子才能接水
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
// 记录当前左右最大高度
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// 哪边低就从哪边计算水量
if (height[left] < height[right]) {
water += leftMax - height[left];
left++;
} else {
water += rightMax - height[right];
right--;
}
}
return water;
}
代码解释
- 边界处理：若数组长度小于3，直接返回0，因为无法形成蓄水槽。
- 双指针遍历：
left和right从两端向中间移动，每次移动较矮的一侧指针。 - 计算水量：当前位置的蓄水量为左右最大高度的较小值减去当前高度，若结果为负则取0（即不蓄水）。
- 动态更新最大高度：每次移动指针时，更新对应方向的最大高度，确保后续计算正确。
示例分析
以数组[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]为例：
- 初始状态：
left=0,right=11,leftMax=0,rightMax=3 - 第一次循环：
height[0]=0 < height[11]=1，水量增加0-0=0，left=1 - 第二次循环：
height[1]=1 < height[11]=1，水量增加1-1=0，left=2 - 第三次循环：
height[2]=0 < height[11]=1，水量增加1-0=1，left=3 - 继续遍历：随着指针移动，每次计算当前位置蓄水量，最终累加得到总水量为6。
复杂度分析
- 时间复杂度：O(n)，仅需一次遍历数组。
- 空间复杂度：O(1)，仅使用常数额外空间。
其他解法对比
- 暴力法：对每个位置遍历左右找最大高度，时间复杂度O(n²)，效率低。
- 动态规划：预处理左右最大高度数组，时间O(n)，空间O(n)。
- 单调栈：用栈记录索引，时间O(n)，实现较复杂。
双指针法在保证线性时间复杂度的同时，空间复杂度最优，是该问题的高效解法。