leetcode 42. 接雨水

[xxleyi]

题：

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：

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


// 第 i 个元素能承接的雨水为 leftMax([0, i]) rightMax([i, len)) 当中的小值减去 height[i]
// sum(map(min(leftMax, rightMax) - cur, height))
// 三次遍历，每次遍历的循环不变式各自维护一个变量，较为简单直接
var trap = function(height) {
  if (height.length < 3) {
    return 0
  }
  const leftMax = Array(height.length).fill(height[0])
  const rightMax = Array(height.length).fill(height[height.length - 1])
  for (let i = 1; i < height.length; i++) {
    leftMax[i] = Math.max(leftMax[i- 1], height[i])
  }
  for (let i = height.length - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])
  }

  let rain = 0
  for (let i = 0; i < height.length; i++) {
    rain += Math.min(leftMax[i], rightMax[i]) - height[i]
  }
  return rain
};


// sum(innerRectangle(width * height))
// 将雨水计算切成一个个横条，在维护单调递减栈的过程中计算雨水
// 双层循环，但复杂度为线性，循环不变式的维护具象化为单调栈的维护，不熟悉单调栈的话，不容易想到
var trap = function(height) {
  if (height.length < 3) {
    return 0
  }
  const stack = []
  stack.top = function() {
    return this[this.length - 1]
  }

  let rain = 0
  for (let i = 0; i < height.length; i++) {
    while(stack.length > 0 && height[i] > height[stack.top()]) {
      const bottom = stack.pop()
      if (stack.length === 0) {
        break
      }
      const leftTop = stack.top()
      const width = i - leftTop - 1
      const h = Math.min(height[i], height[leftTop]) - height[bottom]
      rain += h * width
    }
    stack.push(i)
  }
  return rain
}

// sum(map(min(leftMax, rightMax) - cur, height))
// 仔细观察一下，发现左右同时遍历，可边更新，边计算
// 方法一可进一步优化为左右双指针，节省一次遍历，以及两个数组
// 这样的话，一次遍历，循环不变式需要同时维护五个变量，不容易想到
var trap = function(height) {
  if (height.length < 3) {
    return 0
  }
  let left = 1
  let right = height.length - 2
  let rain = 0
  let leftMax = height[0]
  let rightMax = height[height.length - 1]
  while (left <= right) {
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])
    if (leftMax < rightMax) {
      rain += leftMax - height[left]
      left++
    } else {
      rain += rightMax - height[right]
      right--
    }
  }
  return rain
}