# [42] 接雨水
给定 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.length
1 <= n <= 2> 10^4
0 <= height[i] <= 10^5
# 思路（暴力解法）
这道题的解法挺巧妙的，我们不能去以一个宏观的层面去看待问题，而要以一个计算机的角度，逐个遍历局部来想问题。
首先我们可以想到，如果我们能够知道每一列上能接多少水，那么我们就可以把每一列上的水加起来，就是最终的答案了。那么每一列能接多少水呢？很简单，只需要将每一列水的上底减去下底，就是该列上能接的水的数量了。
下底好说，就是当前列的柱子高度，那么上底怎么计算呢？我们可以从当前列开始，向左右两侧遍历，找到左右两侧最高的柱子，然后取两者中较小的一个，就是当前列的上底了。当然，如果该列的柱子高度大于等于左右两侧的最高柱子，那么该列上就不会有水了。
通过上述的思路，我们可以直接写出一个暴力写法。
function trap(height: number[]): number {
let res = 0;
for (let i = 0; i < height.length; i++) {
let lMax = 0;
let rMax = 0;
for (let l = 0; l < i; l++) {
if (height[l] > lMax) {
lMax = height[l];
}
}
for (let r = i + 1; r < height.length; r++) {
if (height[r] > rMax) {
rMax = height[r];
}
}
res += Math.max(Math.min(lMax, rMax) - height[i], 0);
}
return res;
}
但这样的做法显然时间复杂度太高，那么如何降低复杂度呢？
# 思路（缓存极值）
我们可以尝试将上述的暴力解法进行优化，我们可以使用动态规划的缓存思想，将每一个位置的左右两侧的最高柱子提前计算出来，这样就可以将时间复杂度降低到 O(n)。
注意到，两侧的柱子无论高矮都是不可能存水的，并且可以当做 lMax 和 rMax 的基准值。
之后我们从左到右遍历一次数组，看看每一列的 height 是否比前一个 height 要大，如果是则更新 lMax[i] = height, 否则 lMax[i] = lMax[i - 1]。
同样的我们也可以从右到左遍历一次数组，用同样的方法得出每一列的 rMax。
经过两次遍历，每一格上的 lMax 和 rMax 都已经计算出来了，我们就可以直接计算每一列上的水量了。
function trap(height: number[]): number {
const len = height.length;
const lMax = Array(len).fill(0);
const rMax = Array(len).fill(0);
// base case
lMax[0] = height[0];
rMax[len - 1] = height[len - 1];
// Get left max height and right max height for each one
for (let i = 1; i < len; i++) {
lMax[i] = Math.max(height[i], lMax[i - 1]);
}
for (let i = len - 2; i >= 0; i--) {
rMax[i] = Math.max(height[i], rMax[i + 1]);
}
// Calculate
let sum = 0;
// exclude both sides
for (let i = 1; i < len - 1; i++) {
sum += Math.min(lMax[i], rMax[i]) - height[i];
}
return sum;
}
# 思路（双指针）
另外，我们也可以换个思路，我们使用收尾指针收缩，确定两侧边界的最高高度。
我们可以发现，使用动态规划的方式来计算 lMax 和 rMax 的时间复杂度是 O(n)，而空间复杂度也是 O(n)，我们可以尝试将空间复杂度降低到 O(1)。
我们可以发现，如果左侧的最高柱子小于右侧，则左侧的柱子一定是短板，当前列最多能接平齐左侧的最高柱子的水。反之则右侧的柱子一定是短板，最多能接平齐右侧的最高柱子的水。这样就能在一次遍历内直接完成计算，非常巧妙。
function trap(height: number[]): number {
let left = 0,
right = height.length - 1;
let leftMax = 0,
rightMax = 0;
let res = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// 如果左侧的最高柱子小于右侧，则左侧的柱子一定是短板，最多能接平齐 leftMax 的水
// 因此在该列上，能接水的格子数为 上底高度 - 下底高度 个
if (leftMax < rightMax) {
res += leftMax - height[left];
left++;
} else {
// 反之则右侧的柱子一定是短板，则计算右侧能接水的格子数量
res += rightMax - height[right];
right--;
}
}
return res;
}
# 思路（单调栈）
我们还可以继续更换思路，使用单调栈来解决这个问题。提前找到左右两侧的最高柱子可以让我们对每一列的水量纵向的进行加法计算。那么我们是不是还能从另一个角度，横向的去计算每一个凹陷的存水面积，相加得到总水量呢？
答案是可以的。我们只需要找到每一个凹陷位置处，左右两侧最近较高的柱子位置，即可得到这一个凹陷的存水面积。
那么如何找到左右两侧最近较高的柱子位置呢？单调栈就可以派上用场了。我们可以从左到右遍历一次数组，维护一个单调递减栈，栈中存储的是柱子的下标。在遍历时，当我们在位置 i 处遇到一个比栈顶元素 curr 高的柱子，那么位置 i 就一定是 curr 的右侧边界了，而左侧边界则一定是排在第二个的栈顶元素。知道了左右两侧的边界，我们就可以计算出凹陷的存水面积了。
function trap(height: number[]): number {
// 单调栈解法。本质上是算左右两边之间横着的雨水面积
let res = 0;
// 维护一个单调递减栈（非增栈）
const stack: number[] = [];
for (let i = 0; i < height.length; i++) {
// 当前位置比栈顶位置更高时，说明栈顶位置 curr 可以接雨水，求的是以 curr 为最低点时离左右最近的高点能存水的面积
while (stack.length > 0 && height[i] >= height[stack[stack.length - 1]]) {
const curr = stack.pop() as number;
// 如果此时栈为空，说明没有左边界，无法接雨水，直接 break
if (stack.length === 0) break;
// 栈中当前的栈顶值即为本次接水的左边界，当前遍历位置 i 为右边界
const left = stack[stack.length - 1];
const w = i - 1 - left;
const h = Math.min(height[left], height[i]) - height[curr];
res += w * h;
}
stack.push(i);
}
return res;
}