介绍

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

实现

JavaScript

/**
 * @param {number[]} height
 * @return {number}
 */

/* 42. Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

Helpful animation of this prompt: https://youtu.be/HmBbcDiJapY?t=51

Given n non-negative integers representing an elevation map where
the width of each bar is 1, compute how much water it is able to trap
after raining.

VIEW ELEVATION MAP ON LEETCODE

Example:

Input:            [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Plan:
iterate through and find left maxes
iterate through and find right maxes
create minheight and assign it to the min(leftmax, rightmax)
if current height(element) < minheight
  push minheight - height into water array
else
  push 0 onto water array

sum up water array and return

left maxes =      [0,0,1,1,2,2,2,2,3,3,3,3]
right maxes =     [3,3,3,3,3,3,3,2,2,2,1,0]
water contained = [0,0,1,0,1,2,1,0,0,1,0,0] -> sum = 6
*/

const trap = (heights) => {
  const maxes = new Array(heights.length).fill(0)

  let leftMax = 0
  for (let i = 0; i < heights.length; i++) {
    const height = heights[i]
    maxes[i] = leftMax
    leftMax = Math.max(leftMax, height)
  }

  let rightMax = 0
  for (let i = heights.length - 1; i >= 0; i -= 1) {
    const height = heights[i]
    const minHeight = Math.min(rightMax, maxes[i])

    if (height < minHeight) maxes[i] = minHeight - height
    else maxes[i] = 0
    rightMax = Math.max(rightMax, height)
  }
  return maxes.reduce((a, b) => a + b, 0)
}