接雨水

• 算法与数据结构
• 2020-12-25 13:32:55

输入：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
}