接雨水

题目

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

提示:

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

示例

输入: 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 个单位的雨水(蓝色部分表示雨水).

题解

JavaScript - 动态规划

对于下标 i, 下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值; 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i].

因此, 对于数组 height 中的每个元素, 我们可以分别向左和向右扫描并记录左边和右边的最大高度. 具体的操作是声明两个数组 leftMax 和 rightMax:

• 当 1 <= i < n 时, 有 leftMax[i] = Math.max(leftMax[i - 1], height[i])
• 当 0 <= i < n - 1 时, 有 rightMax[i] = Math.max(rightMax[i + 1], height[i])

考虑初始值, 显然 leftMax[0] = height[0], rightMax[n - 1] = height[n - 1].

当计算出 leftMax 和 rightMax 后, 通过 Math.min(leftMax[i], rightMax[i]) - height[i] 即可计算出下标 i 处可以接到雨水的数量, 累加之即可.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  const n = height.length

  const leftMax = new Array(n).fill(0)
  const rightMax = new Array(n).fill(0)
  leftMax[0] = height[0]
  rightMax[n - 1] = height[n - 1]

  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i])
  }

  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])
  }

  let ans = 0
  for (let i = 1; i < n; i++) {
    ans += Math.min(leftMax[i], rightMax[i]) - height[i]
  }

  return ans
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

JavaScript - 双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (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])

    // 左指针的 leftMax 比右指针的 rightMax 矮
    // 说明左指针的右边至少有一个板子 > 左指针左边所有板子
    // 根据水桶效应, 保证了左指针当前列的水量决定权在左边
    // 那么可以计算左指针当前列的水量: 左边最大高度 - 当前列高度
    if (height[left] < height[right]) {
      ans += leftMax - height[left]
      left++
    } else {
      ans += rightMax - height[right]
      right--
    }
  }

  return ans
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

JavaScript - 单调栈

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  const stack = []
  const n = height.length
  let ans = 0

  for (let i = 0; i < n; ++i) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop()

      if (!stack.length) {
        break
      }

      const left = stack[stack.length - 1]
      const currWidth = i - left - 1
      const currHeight = Math.min(height[left], height[i]) - height[top]
      ans += currWidth * currHeight
    }

    stack.push(i)
  }

  return ans
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

Rust

动态规划版

use std::cmp;

pub fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();

    // 由于下面使用到了 n - 2 这个索引, 因此当 n 为 1 时直接返回 0
    if n == 1 {
        return 0;
    }

    let mut left_max = vec![0; n];
    let mut right_max = vec![0; n];
    left_max[0] = height[0];
    right_max[n - 1] = height[n - 1];

    for i in 1..n {
        left_max[i] = cmp::max(left_max[i - 1], height[i]);
    }

    for i in (0..=(n - 2)).rev() {
        right_max[i] = cmp::max(right_max[i + 1], height[i]);
    }

    let mut ans = 0;
    for i in 1..n {
        ans += cmp::min(left_max[i], right_max[i]) - height[i];
    }

    ans
}

双指针版

use std::cmp;

pub fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();
    let (mut left_max, mut right_max) = (0, 0);
    let (mut left, mut right) = (0, n - 1);
    let mut ans = 0;

    while left < right {
        left_max = cmp::max(left_max, height[left]);
        right_max = cmp::max(right_max, height[right]);

        if height[left] < height[right] {
            ans += left_max - height[left];
            left += 1;
        } else {
            ans += right_max - height[right];
            right -= 1;
        }
    }

    ans
}

单调栈版

use std::cmp;

pub fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();
    let mut stack: Vec<usize> = vec![];
    let mut ans = 0;

    for i in 0..n {
        while stack.len() > 0 && height[i] > height[*stack.last().unwrap()] {
            let top = stack.pop().unwrap();

            if stack.len() == 0 {
                break;
            }

            let left = *stack.last().unwrap();
            let curr_width = (i - left - 1) as i32;
            let curr_height = cmp::min(height[left], height[i]) - height[top];
            ans += curr_width * curr_height;
        }

        stack.push(i);
    }

    ans
}