接雨水问题

11. 盛最多水的容器 (opens new window)

// 双指针 求左右两边最小高度面积
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  const n = height.length
  let left = 0
  let right = n - 1
  let max = 0
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left)
    max = Math.max(area, max)
    if (height[left] < height[right]) {
      left++
    } else {
      right--
    }
  }
  return max
}

42. 接雨水 (opens new window)

// 将每个水柱拆开来看
// water[i] = min(
//            # 左边最高的柱子
//            max(height[0..i]),
//            # 右边最高的柱子
//            max(height[i..end])
//         ) - height[i]
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  const n = height.length
  let left = 0
  let right = n - 1
  let lMax = 0
  let rMax = 0
  let res = 0
  while (left < right) {
    lMax = Math.max(lMax, height[left])
    rMax = Math.max(rMax, height[right])
    if (height[left] < height[right]) {
      res += lMax - height[left]
      left++
    } else {
      res += rMax - height[right]
      right--
    }
  }
  return res
}