42. Trapping Rain Water

解法1:

通过两个数组记录前缀和（包括自己的高度），后缀和

Array(n):

arrayLength

如果传递给 Array 构造函数的唯一参数是介于 0 到 232 - 1（含）之间的整数，这将返回一个新的 JavaScript 数组，其 length 属性设置为该数字（注意：这意味着一个由 arrayLength 个空槽组成的数组，而不是具有实际 undefined 值的槽——参见稀疏数组）。

/**
 * @param {number[]} height
 * @return {number}
 */
// 前后缀和法
var trap = function (height) {
  // prefix
  const n = height.length
  const prefix = [height[0]]
  const surfix = Array(n).fill(0) // 重复元素
  surfix[n - 1] = height[n - 1]
  const ans = []
  // prefix
  for (let i = 1; i < n; i++) {
    prefix.push(Math.max(prefix[i - 1], height[i]))
  }
  // surfix
  for (let i = n - 2; i > -1; i--) {
    surfix[i] = Math.max(surfix[i + 1], height[i])
  }
  for (let i = 0; i < n; i++) {
    ans.push(Math.min(surfix[i], prefix[i]) - height[i])
  }
  return ans.reduce((acc, cur) => acc + cur, 0)
}

解法二（双指针）：

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

// 思路：用双指针代表前后缀和，一个bucket的水位高度由最小的前/后缀决定
var trap = function (height) {
  const n = height.length
  let left = 0,
    right = n - 1
  let pre_max = height[left],
    suf_max = height[right]
  let ans = 0
  // 可不加等号, 相遇点一定最高
  while (left < right) {
    // 如果前缀和最小，则移动left指针。
    if (pre_max < suf_max) {
      ans += Math.min(pre_max, suf_max) - height[left]
      left++
      pre_max = Math.max(pre_max, height[left])
    } else {
      ans += Math.min(pre_max, suf_max) - height[right]
      right--
      suf_max = Math.max(suf_max, height[right])
    }
  }
  return ans
}