42. Trapping Rain Water

假设每个位置都有一个宽度是1的桶，

能接多少水取决于 min(左边木板的高度，右边木板的高度)

左边木板的高度取决于左边的最大高度

第一个数组存从最左边到第i个位置的最大高度（前缀的最大值）

第二个数组存从最右边到第i个位置的最大高度（后缀的最大值）

前缀：

后缀

解法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}
 */
var trap = function (height) {
  // ans: 最终能接的雨水总量，初始化为0
  // preMax: 从左到右遍历过程中，记录左侧遇到的最大柱子高度
  // sufMax: 从右到左遍历过程中，记录右侧遇到的最大柱子高度
  let ans = 0,
    preMax = 0,
    sufMax = 0

  // left: 左指针，初始指向数组第一个元素
  // right: 右指针，初始指向数组最后一个元素
  let left = 0,
    right = height.length - 1

  // 双指针遍历，直到左右指针相遇
  while (left < right) {
    // 更新左侧最大高度：取当前preMax和左指针位置柱子高度的较大值
    preMax = Math.max(preMax, height[left])
    // 更新右侧最大高度：取当前sufMax和右指针位置柱子高度的较大值
    sufMax = Math.max(sufMax, height[right])

    // 核心逻辑：哪边的最大高度更小，就计算哪边的接水量
    if (preMax < sufMax) {
      // 左指针位置能接的水量 = 左侧最大高度 - 当前柱子高度
      ans += preMax - height[left]
      // 左指针右移
      left++
    } else {
      // 右指针位置能接的水量 = 右侧最大高度 - 当前柱子高度
      ans += sufMax - height[right]
      // 右指针左移
      right--
    }
  }

  // 返回总接水量
  return ans
}