1、题目
给定 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
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
2、题解
核心要点是：
水总会往地处流动,总会从短处流出,所以这是个瓶颈问题
- 1. 当前柱子的积水深度只与最左侧和最右侧的柱子之中最短的那个柱子高度有关系
- 2. 当前柱子的积水深度与左右柱子内部的地形无关
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
const n = height.length;
let left = 0, right = n - 1;
let leftMax = 0, rightMax = 0;
let rain = 0;
// 遍历高度图直到两个指针相遇
while(left < right) {
// 更新左右两边遇到的最大的墙的高度
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// 根据哪边的墙更短来决定积水的位置，并移动指针
if (leftMax < rightMax) {
// 如果左边的墙更短，则在当前左指针位置积水
// 积水量等于左侧最大高度减去当前高度
rain += leftMax - height[left];
// 移动左指针
left++;
} else {
// 如果右边的墙更短，则在当前右指针位置积水
// 积水量等于右侧最大高度减去当前高度
rain += rightMax - height[right];
// 移动右指针
right--;
}
}
// 返回总的积雨水量
return rain;
};3、总结
时间复杂度:
- O(n)：因为整个数组被遍历一次，其中n是数组
height的长度。
空间复杂度:
- O(1)：使用了固定数量的变量，无论输入数组的大小如何，额外空间的使用量都保持不变。
这个算法的精妙之处在于利用两个指针从两端向中间扫描，同时计算出每个位置能够积累的雨水量。通过在扫描过程中更新左右两侧的最大高度值，可以保证计算积水量时总是以较低的一边作为参考高度，这样就能准确地计算出每一步的积水量，同时避免了不必要的重复计算或回溯，保证了算法的效率和准确性。