接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
codeType
输入：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：
codeType
输入：height = [4,2,0,3,2,5]
输出：9
提示：
codeType
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
解法一：
暴力法 + 贪心。这题和发糖果那题很像（同样是需要同时满足左规则和右规则），位置i的接雨水的最高高度为位置i的左边最高墙和右边最高墙中矮的那个。所以只要求出位置i的左边最高墙和右边最高墙，就能得到答案。每个位置找左边最高墙和右边最高墙需要遍历一遍数组，所以时间复杂度是O(n)。n个位置找n遍，所以最终的时间复杂度时O(n^2)。
以下题解存在很多可以优化的地方。写这么臃肿主要是为了代码更直观更好懂。
typescript
function trap(height: number[]): number {
// 暴力法
// 位置i的左面最高墙为L[i],右面最高墙为R[i] （其实就是假设右边无限高/左边无限高,感觉和发糖果那题很像）
// 那么位置i接水后所能达到的最高高度h[i]就是，min(L[i], R[i])
// 那么位置i的水量就是最高高度-位置i的高度也就是max(h[i] - height[i],0) 不能小于0
// 所以只要得到数组L和数组R就能解答
const n = height.length
const L: number[] = new Array(n).fill(0)
const R: number[] = new Array(n).fill(0)
const res: number[] = new Array(n).fill(0)
L[0] = 0
for(let i=1; i<n; i++){
let LeftMax = 0
// 求位置i的L数组
for(let j=0; j<i; j++){
// 找位置i左边的最大值,从0开始遍历到i-1
LeftMax = Math.max(LeftMax, height[j])
}
L[i] = LeftMax
}
R[n-1] = 0
for(let i=n-2; i>=0; i--){
let RightMax = 0
for(let j=n-1; j>i; j--){
// 找位置i右边的最大值，从n-1开始遍历到i+1
RightMax = Math.max(RightMax, height[j])
}
R[i] = RightMax
}
for(let i=0; i<n; i++){
res[i] = Math.max(Math.min(L[i], R[i]) - height[i], 0) // 每个位置能接的雨水量
}
let sum = 0
res.forEach(num => {
sum += num
})
return sum
};
解法二：
动态规划：上一个解法当中存在很多可以优化的地方，特别是求L数组和R数组的过程，这个过程中存在很多重复的操作，可以用动态规划的方式进行优化。观察下面的解题过程我们会发现，求L的时候，L[i] = Max(L[i-1), height[i-1])，也就是说，求L[i]的时候并不需要遍历整个height。R数组同理。求L和R的时间复杂度被降低到O(n)，所以整体的时间复杂度就降到了O(n)
typescript
function trap(height: number[]): number {
// 动态规划
const n = height.length
const L: number[] = new Array(n).fill(0)
const R: number[] = new Array(n).fill(0)
const res: number[] = new Array(n).fill(0)
L[0] = 0
for(let i=1; i<n; i++){
L[i] = Math.max(L[i-1], height[i-1]) // 简化了求L和R的过程
}
R[n-1] = 0
for(let i=n-2; i>=0; i--){
R[i] = Math.max(R[i+1], height[i+1])
}
for(let i=0; i<n; i++){
res[i] = Math.max(Math.min(L[i], R[i]) - height[i], 0) // 每个位置能接的雨水量
}
let sum = 0
res.forEach(num => {
sum += num
})
return sum
};