给定 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
const trap = function (height) {
if (height.length === 0) {
return 0;
}
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
// 较矮的一侧决定当前能接多少水，因为另一侧已经有更高或相等的边界。
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
const result = trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]);
console.log(result);
const result2 = trap([4, 2, 0, 3, 2, 5]);
console.log(result2);这个解法的思路很容易，其实就是要想到每一格能装多少雨水 每一格能装的雨水，等于当前格左边的最高的位置与右边最高的位置中小的哪一个 然后减去当前位置的数量，
function trap(height = []) {
if (height === 0) {
return 0;
}
const n = height.length;
let res = 0;
for (let i = 1; i < n - 1; i++) {
let l_max = 0;
let r_max = 0;
for (let j = i; j < n; j++) {
// 找到右边的最大值
r_max = Math.max(r_max, height[j]);
}
for (let j = i; j >= 0; j--) {
// 找到左边的最大值
l_max = Math.max(l_max, height[j]);
}
// 这里需要判断一下，如果当前格子的数量比左右两边最高的都高，那么当前就是0，不能是负数
// res += Math.min(l_max, r_max) - height[i];
let current = Math.min(l_max, r_max) - height[i];
res += current > 0 ? current : 0;
}
return res;
}这个的时间复杂度是 O(N^2) 空间复杂度是 O(1) 因为只是使用了 l_max/r_max 这种单个基础值的变量
如何优化呢，首先要想到，可不可以先求出每格的左边最大值和右边最大值这两个的最小值 max，存储起来 然后在一个 for 循环里直接去找当前格的 max 求差值
如何先求出当前每格的最大值和右边最大值这两个的最小值 max 呢？
把这个思路的图放下来吧(这个思路太牛逼了)
function trap(height = []) {
if (!height.length) {
return 0;
}
const n = height.length;
let res = 0;
let l_max = Array(n);
let r_max = Array(n);
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// 计算 l_max，从左到右
for (let i = 1; i < n; i++) {
l_max[i] = Math.max(height[i], l_max[i - 1]);
}
// 计算 r_max，从右到左
for (let i = n - 2; i >= 0; i--) {
r_max[i] = Math.max(height[i], r_max[i + 1]);
}
// 要明白第一个和最后一个是装不了水的，所以从第0和第n个都不能计算
for (let i = 1; i < n - 1; i++) {
res += Math.min(l_max[i], r_max[i]) - height[i];
}
return res;
}这个优化其实和暴力解法思路差不多，就是避免了重复计算，把时间复杂度降低为 O(N)，已经是最优了 但是空间复杂度是 O(N)
第三种解法，双指针法，实时计算两边的 l_max/r_max 这个解法使用双指针太牛逼了，真是太牛逼了 看下官方题解的动图
复杂度分析： 时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。 空间复杂度：O(1)。只需要使用常数的额外空间。
function trap(height = []) {
if (height.length === 0) {
return;
}
let ans = 0;
let left = 0,
right = height.length - 1;
let leftMax = 0,
rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
/*
这里写 if (height[left] > height[right]) 也是对的，但是很不好理解，原因见下面的解释
*/
if (leftMax < rightMax) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}【方法三必有的解释】不知道你是否和我一样，对方法三的 “必有” 感到困惑：
- 如果
height[left] < height[right]，则必有leftMax < rightMax - 如果
height[left] >= height[right]，则必有leftMax >= rightMax
这是因为我们忽视了代码中的一个细节：
if (height[left] < height[right]) {
left++;
} else {
right--;
}如果当前轮的双指针为 left 和 right，那么上一轮要么是 left - 1 和 right，要么是 left 和 right + 1。
- 如果移动的是
left指针，即left - 1->left，那么height[0, left- 1] < height[right]且height[right] = rightMax - 如果移动的是
right指针，即right<-right + 1，那么height[left] >= height[right + 1, n - 1]且height[left] = leftMax
现在，我们再回看官方的描述： 如果 height[left] < height[right]，则必有 leftMax < rightMax
- 假设上一轮移动的是
left指针，有height[0, left- 1] < height[right]，又height[left] < height[right]，则height[0, left] < height[right] = rightMax - 假设上一轮移动的是
right指针，有height[left] >= height[right + 1, n - 1]，又height[left] < height[right]，则leftMax = height[left] < height[right]
最后，我觉得虽然官方的代码没有问题，但还是直接比较 leftMax 和 rightMax 的写法会更好理解：
以上解释来自 评论区 inuter
双指针法能用在很多地方，比如在求数组内求和等于 n 有多少种方式时，就可以先排序 然后使用双指针法
参考下视频
使用 双指针 作为关键字去 ytb/bilibili 上搜索一下