zhangdizhangdi

42. 接雨水 🟥

题目

leetcode 困难

题目

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

示例1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例2：
输入：height = [4,2,0,3,2,5]
输出：9

题解

思路

“前后缀数组”和“双指针”解法，它们都有一个共同的特征：“按列求水”（竖着算）。每一次计算的都是某单一根柱子上方能积攒的细长条水柱。
而单调栈解法的思路有着本质的区别：它是 “按层求水”（横着算）。每一次计算的是两堵墙之间形成的一个“横向的水洼”。

方法：前后缀数组/动态规划

解题思路

想象一下，你站在第 i 列柱子上，左右两边各有一堵很高的墙。
这块地方能积多少水，取决于左右两边最矮的那堵墙（木桶效应）。

  • 找到左边最高的柱子，高度记作 leftMax。
  • 找到右边最高的柱子，高度记作 rightMax。
  • 水面的高度就是这两者里的较小值：Math.min(leftMax, rightMax)。
  • 第 i 列实际上能积水的量，就是水面高度减去当前柱子本身的高度：
    当前列积水量 = Math.min(leftMax, rightMax) - height[i]
复杂度
  • 时间复杂度：O(n)

    n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次，计算能接的雨水总量还需要遍历一次。

  • 空间复杂度：O(n)

    n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。

js
function trap(height) {
  const n = height.length
  if (n == 0) {
    return 0
  }

  const leftMax = new Array(n).fill(0)
  leftMax[0] = height[0]
  for (let i = 1; i < n; ++i) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i])
  }
  console.log('leftMax', leftMax)

  const rightMax = new Array(n).fill(0)
  rightMax[n - 1] = height[n - 1]
  for (let i = n - 2; i >= 0; --i) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])
  }
  console.log('rightMax', rightMax)

  let ans = 0
  for (let i = 0; i < n; ++i) {
    const minHeight = Math.min(leftMax[i], rightMax[i])
    const trappedWater = minHeight - height[i]
    console.log('i', i, 'minHeight', minHeight, 'trappedWater', trappedWater)
    ans += trappedWater
  }
  return ans
}

console.log('🌰', trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
console.log('------------------')
console.log('🌰', trap([4, 2, 0, 3, 2, 5]))
执行结果
leftMax [
  0, 1, 1, 2, 2,
  2, 2, 3, 3, 3,
  3, 3
]
rightMax [
  3, 3, 3, 3, 3,
  3, 3, 3, 2, 2,
  2, 1
]
i 0 minHeight 0 trappedWater 0
i 1 minHeight 1 trappedWater 0
i 2 minHeight 1 trappedWater 1
i 3 minHeight 2 trappedWater 0
i 4 minHeight 2 trappedWater 1
i 5 minHeight 2 trappedWater 2
i 6 minHeight 2 trappedWater 1
i 7 minHeight 3 trappedWater 0
i 8 minHeight 2 trappedWater 0
i 9 minHeight 2 trappedWater 1
i 10 minHeight 2 trappedWater 0
i 11 minHeight 1 trappedWater 0
🌰 6
------------------
leftMax [ 4, 4, 4, 4, 4, 5 ]
rightMax [ 5, 5, 5, 5, 5, 5 ]
i 0 minHeight 4 trappedWater 0
i 1 minHeight 4 trappedWater 2
i 2 minHeight 4 trappedWater 4
i 3 minHeight 4 trappedWater 1
i 4 minHeight 4 trappedWater 2
i 5 minHeight 5 trappedWater 0
🌰 9

方法：首尾双指针

复杂度
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
js
function trap(height) {
  let ans = 0
  let left = 0,
    right = height.length - 1
  let leftMax = 0,
    rightMax = 0
  while (left < right) {
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])

    console.log('♻️ left:', left, 'right:', right, 'leftMax:', leftMax, 'rightMax:', rightMax, 'height[left]:', height[left], 'height[right]:', height[right])

    if (height[left] < height[right]) {
      console.log('接水 leftMax - height[left]：', leftMax - height[left])

      ans += leftMax - height[left]
      ++left
    } else {
      console.log('接水 rightMax - height[right]：', rightMax - height[right])

      ans += rightMax - height[right]
      --right
    }
  }
  return ans
}

console.log('🌰', trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
console.log('------------------')
console.log('🌰', trap([4, 2, 0, 3, 2, 5]))
执行结果
♻️ left: 0 right: 11 leftMax: 0 rightMax: 1 height[left]: 0 height[right]: 1
接水 leftMax - height[left]： 0
♻️ left: 1 right: 11 leftMax: 1 rightMax: 1 height[left]: 1 height[right]: 1
接水 rightMax - height[right]： 0
♻️ left: 1 right: 10 leftMax: 1 rightMax: 2 height[left]: 1 height[right]: 2
接水 leftMax - height[left]： 0
♻️ left: 2 right: 10 leftMax: 1 rightMax: 2 height[left]: 0 height[right]: 2
接水 leftMax - height[left]： 1
♻️ left: 3 right: 10 leftMax: 2 rightMax: 2 height[left]: 2 height[right]: 2
接水 rightMax - height[right]： 0
♻️ left: 3 right: 9 leftMax: 2 rightMax: 2 height[left]: 2 height[right]: 1
接水 rightMax - height[right]： 1
♻️ left: 3 right: 8 leftMax: 2 rightMax: 2 height[left]: 2 height[right]: 2
接水 rightMax - height[right]： 0
♻️ left: 3 right: 7 leftMax: 2 rightMax: 3 height[left]: 2 height[right]: 3
接水 leftMax - height[left]： 0
♻️ left: 4 right: 7 leftMax: 2 rightMax: 3 height[left]: 1 height[right]: 3
接水 leftMax - height[left]： 1
♻️ left: 5 right: 7 leftMax: 2 rightMax: 3 height[left]: 0 height[right]: 3
接水 leftMax - height[left]： 2
♻️ left: 6 right: 7 leftMax: 2 rightMax: 3 height[left]: 1 height[right]: 3
接水 leftMax - height[left]： 1
🌰 6
------------------
♻️ left: 0 right: 5 leftMax: 4 rightMax: 5 height[left]: 4 height[right]: 5
接水 leftMax - height[left]： 0
♻️ left: 1 right: 5 leftMax: 4 rightMax: 5 height[left]: 2 height[right]: 5
接水 leftMax - height[left]： 2
♻️ left: 2 right: 5 leftMax: 4 rightMax: 5 height[left]: 0 height[right]: 5
接水 leftMax - height[left]： 4
♻️ left: 3 right: 5 leftMax: 4 rightMax: 5 height[left]: 3 height[right]: 5
接水 leftMax - height[left]： 1
♻️ left: 4 right: 5 leftMax: 4 rightMax: 5 height[left]: 2 height[right]: 5
接水 leftMax - height[left]： 2
🌰 9

方法：单调栈

复杂度
  • 时间复杂度：O(n)

    n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。

  • 空间复杂度：O(n)

    n 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。

js
function trap(height) {
  let ans = 0
  const stack = []
  const n = height.length

  for (let i = 0; i < n; ++i) {
    console.log('♻️ i', i, 'height[i]', height[i], 'stack', stack.toString())

    // 发现当前柱子比栈顶的柱子高，说明遇到“右边界”了，可以找坑算水了！
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      // 1. 弹出栈顶，它是“坑底”
      const bottomIdx = stack.pop()

      console.log('🕳️ bottomIdx', bottomIdx)

      // 如果弹出来之后栈空了，说明左边没有更高的墙挡着，兜不住水，直接退出循环
      if (stack.length === 0) {
        break
      }

      // 2. 此时的新栈顶，就是“左边界”
      const leftIdx = stack[stack.length - 1]

      // 3. 计算宽度：右边界 - 左边界 - 1 (中间夹着的距离)
      const width = i - leftIdx - 1

      // 4. 计算高度：左右边界较矮的那个，减去坑底的高度
      const h = Math.min(height[leftIdx], height[i]) - height[bottomIdx]

      console.log(
        'leftIdx',
        leftIdx,
        'width',
        width,
        'h',
        h,
        '接💦：',
        width * h,
      )

      // 5. 累加这一个横向层面的积水
      ans += width * h
    }

    // 如果当前柱子比栈顶矮，或者上面一顿操作算完水了，就把当前柱子入栈，等待将来的右边界
    stack.push(i)
  }
  return ans
}

console.log('🌰', trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
console.log('------------------')
console.log('🌰', trap([4, 2, 0, 3, 2, 5]))
执行结果
♻️ i 0 height[i] 0 stack 
♻️ i 1 height[i] 1 stack 0
🕳️ bottomIdx 0
♻️ i 2 height[i] 0 stack 1
♻️ i 3 height[i] 2 stack 1,2
🕳️ bottomIdx 2
leftIdx 1 width 1 h 1 接💦： 1
🕳️ bottomIdx 1
♻️ i 4 height[i] 1 stack 3
♻️ i 5 height[i] 0 stack 3,4
♻️ i 6 height[i] 1 stack 3,4,5
🕳️ bottomIdx 5
leftIdx 4 width 1 h 1 接💦： 1
♻️ i 7 height[i] 3 stack 3,4,6
🕳️ bottomIdx 6
leftIdx 4 width 2 h 0 接💦： 0
🕳️ bottomIdx 4
leftIdx 3 width 3 h 1 接💦： 3
🕳️ bottomIdx 3
♻️ i 8 height[i] 2 stack 7
♻️ i 9 height[i] 1 stack 7,8
♻️ i 10 height[i] 2 stack 7,8,9
🕳️ bottomIdx 9
leftIdx 8 width 1 h 1 接💦： 1
♻️ i 11 height[i] 1 stack 7,8,10
🌰 6
------------------
♻️ i 0 height[i] 4 stack 
♻️ i 1 height[i] 2 stack 0
♻️ i 2 height[i] 0 stack 0,1
♻️ i 3 height[i] 3 stack 0,1,2
🕳️ bottomIdx 2
leftIdx 1 width 1 h 2 接💦： 2
🕳️ bottomIdx 1
leftIdx 0 width 2 h 1 接💦： 2
♻️ i 4 height[i] 2 stack 0,3
♻️ i 5 height[i] 5 stack 0,3,4
🕳️ bottomIdx 4
leftIdx 3 width 1 h 1 接💦： 1
🕳️ bottomIdx 3
leftIdx 0 width 4 h 1 接💦： 4
🕳️ bottomIdx 0
🌰 9