动态规划（DP）解积雨问题
示例：输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
下面我们来思考如何找到每个柱子两侧中最高的柱子分别是多少，我们用两个循环来尝试解决：
//伪代码//寻找柱子k的左侧最高柱子for(i = 0 - > k）leftMax = Math.max(arr[i], leftMax)
//伪代码//寻找柱子k的右侧最高柱子for(i = k - > arr.length）rightMax = Math.max(arr[i], rightMax)
已经解决了如何寻找某个柱子左右侧的最高柱子，那么我们就可以求出每个柱子的积水量，再求和即可：
// 因为不是最终解法，所以我是盲写的代码function getWater(arr){let sum = 0for(let i = 0; i < arr.length; i++){let leftMax = 0let rightMax = 0for(let n = 0; n < i; n++){leftMax = Math.max(arr[n], leftMax)}for(let m = i; m < arr.length; m++){rightMax = Math.max(arr[m], rightMax)}let v = Math.min(leftMax, rightMax) - arr[i]// 如果当前柱子比左右侧最高柱子高，则他的积雨体积就是0sum += height ? height : 0}}
时间复杂度O(n^2), 我们可以看一下是否还有更好的解法。题目上已经提到了要用动归的思路去解决，那我们看看如何进行优化：
我们回到刚才求某个节点左右侧最高柱子的问题，是否可以只进行一次循环就把所有的柱子的两侧最高柱子分别求出来：
max(左侧临近第一个柱子的左侧最高, 当前柱子)
max(右侧临近第一个柱子的右侧最高, 当前柱子)
//求所有柱子的左侧最高柱子for(i = 0 - > arr.length）leftDP[i] = Math.max(leftDP[i - 1], height[i])
//求所有柱子的右侧最高柱子for(i = arr.length - > 0）rightDP[i] = Math.max(rightDP[i + 1], height[i])
然后在循环一遍来计算每个柱子的存水高度，求和即可。请看完整代码：
/*** @param {number[]} height* @return {number}*/var trap = function(height) {// dp方案let len = height.lengthlet l = [height[0]] // 初始化左侧最高点数组let r = [] // 初始化右侧最高点数组r[len - 1] = height[len - 1]let v = [0] // 初始化高度数组v[len - 1] = 0let result = 0for(let i = 1; i < len; i++){l[i] = Math.max(l[i - 1], height[i])}for(let i = len - 2; i >= 0; i--){r[i] = Math.max(r[i + 1], height[i])}for(let i = 1; i < len - 1; i ++){v[i] = Math.max((Math.min(l[i], r[i]) - height[i]), 0)result += v[i]}// 求和return result};
到此，我们已经完成了用简单的DP思路来优化了两层循环（时间复杂度O(n^2)）的效率问题，但是我们使用了三个数组来进行存储，给大家留一个思考题，我们是否能有一个既优化时间又优化空间的算法来解决积水问题呢？
明天，我会写其他常见的用动态规划来解决的问题合集，大家尽请期待。
如果你觉得文章的内容能给你带来收获，欢迎关注 + 点赞在看 + 转发，更期待你能推荐给身边的小伙伴，让我们一起来梳理前端知识！一起加油！
文章涉及到源码已经在github中开源
快点他！让我知道你在看！