
接雨水
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6
解法:动态规划
/** * @description 接雨水 * @param {number[]} height * @return {number} */ const trap = (height) => { let waterAmount = 0 const len = height.length const leftMaxLevels = [] const rightMaxLevels = [] // 统计左边数组的最大值 leftMaxLevels[0]=height[0] for (let i = 1; i < len; i++) { leftMaxLevels[i] = Math.max(height[i], leftMaxLevels[i-1]) } // 统计右边数组的最大值 rightMaxLevels[len - 1] = height[len - 1] for (let i = len - 2; i >= 0; i--) { rightMaxLevels[i] = Math.max(height[i], rightMaxLevels[i + 1]) } // 求每一列的面积和 for (let i = 0; i < len; i++) { waterAmount += Math.min(leftMaxLevels[i], rightMaxLevels[i]) - height[i] } return waterAmount }
评论(0)