notes | Kisstar

# 42. 接雨水

# 解题思路

  • 暴力解法：
    • 遍历数组，将元素逐个放入栈中，计算当前元素与栈顶元素的差值，如果大于 0，则说明可能会盛水，因此此时进入计算当前可以盛水的量。
    • 计算时判断，首先判断当前元素和栈顶的大小，它们中的最小值即为其中每一项可能盛水量的最大值，因为将每一项与其做差值就能获得该项的盛水量。
    • 需要注意，判断时需要从栈顶往栈低开始遍历，同时判断，如果某一项的值大于了当前元素，则说明后续的边界不可能和当前元素组成的边界盛水，因此可以跳过。
    • 最后，需要判断如果当前元素大于栈顶元素，则说明新的元素将会代替栈顶元素，作为新的边界，此时清空栈，否则，我们把每一项盛水量的值都提升到和当前元素相同，这样才可以保证后面出现更高的边界和栈底下面的值组成边界时得到正确的盛水量。
var trap = function (height) {
  let stack = []
  let len = height.length
  let total = 0

  for (let i = 0; i < len; i++) {
    let cur = height[i]
    let top = stack[stack.length - 1] || 0

    if (cur >= top) {
      // 如果左边界没有值，那么出现的零是没有意义的
      if (stack.length === 0 && cur === 0) {
        continue
      }

      // 如果出现了大于或等于左边界的值，则可以结算看是否可以盛水
      total += calculateTotal(stack, cur)
    } else {
      stack.push(cur)
    }
  }

  return total
}

function calculateTotal(pool, nEdge) {
  let total = 0
  let len = pool.length
  let rEdge = pool[0]
  // 为真表示出现了新的最高边界，在计算后需要清空栈，作为新的左边界
  // 否则只是出现了可能盛水的边界，计算后把其中小于该边界的边界提升到和当前边界值一致
  const isNewTop = nEdge > rEdge
  const edge = Math.min(nEdge, rEdge)

  for (let i = len - 1; i >= 0; i--) {
    let cur = pool[i]

    if (cur > edge) {
      break
    }

    total += edge - cur

    if (!isNewTop) {
      pool[i] = edge
    }
  }

  if (isNewTop) {
    pool.length = 0
  }

  pool.push(nEdge)

  return total
}

# 参考

← 队列 →