Question

面试题 17.21. 直方图的水量

English Version

题目描述

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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

解法

方法一：动态规划

我们定义 $left[i]$ 表示下标 $i$ 位置及其左边的最高柱子的高度，定义 $right[i]$ 表示下标 $i$ 位置及其右边的最高柱子的高度。那么下标 $i$ 位置能接的雨水量为 $min(left[i], right[i]) - height[i]$。我们遍历数组，计算出 $left[i]$ 和 $right[i]$，最后答案为 $\sum_{i=0}^{n-1} min(left[i], right[i]) - height[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

相似题目：

• 42. 接雨水

class Solution:
  def trap(self, height: List[int]) -> int:
    n = len(height)
    if n < 3:
      return 0
    left = [height[0]] * n
    right = [height[-1]] * n
    for i in range(1, n):
      left[i] = max(left[i - 1], height[i])
      right[n - i - 1] = max(right[n - i], height[n - i - 1])
    return sum(min(l, r) - h for l, r, h in zip(left, right, height))

class Solution {
  public int trap(int[] height) {
    int n = height.length;
    if (n < 3) {
      return 0;
    }
    int[] left = new int[n];
    int[] right = new int[n];
    left[0] = height[0];
    right[n - 1] = height[n - 1];
    for (int i = 1; i < n; ++i) {
      left[i] = Math.max(left[i - 1], height[i]);
      right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += Math.min(left[i], right[i]) - height[i];
    }
    return ans;
  }
}

class Solution {
public:
  int trap(vector<int>& height) {
    int n = height.size();
    if (n < 3) {
      return 0;
    }
    int left[n], right[n];
    left[0] = height[0];
    right[n - 1] = height[n - 1];
    for (int i = 1; i < n; ++i) {
      left[i] = max(left[i - 1], height[i]);
      right[n - i - 1] = max(right[n - i], height[n - i - 1]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += min(left[i], right[i]) - height[i];
    }
    return ans;
  }
};

func trap(height []int) (ans int) {
  n := len(height)
  if n < 3 {
    return 0
  }
  left := make([]int, n)
  right := make([]int, n)
  left[0], right[n-1] = height[0], height[n-1]
  for i := 1; i < n; i++ {
    left[i] = max(left[i-1], height[i])
    right[n-i-1] = max(right[n-i], height[n-i-1])
  }
  for i, h := range height {
    ans += min(left[i], right[i]) - h
  }
  return
}

function trap(height: number[]): number {
  const n = height.length;
  if (n < 3) {
    return 0;
  }
  const left: number[] = new Array(n).fill(height[0]);
  const right: number[] = new Array(n).fill(height[n - 1]);
  for (let i = 1; i < n; ++i) {
    left[i] = Math.max(left[i - 1], height[i]);
    right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
  }
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    ans += Math.min(left[i], right[i]) - height[i];
  }
  return ans;
}

public class Solution {
  public int Trap(int[] height) {
    int n = height.Length;
    if (n < 3) {
      return 0;
    }
    int[] left = new int[n];
    int[] right = new int[n];
    left[0] = height[0];
    right[n - 1] = height[n - 1];
    for (int i = 1; i < n; ++i) {
      left[i] = Math.Max(left[i - 1], height[i]);
      right[n - i - 1] = Math.Max(right[n - i], height[n - i - 1]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += Math.Min(left[i], right[i]) - height[i];
    }
    return ans;
  }
}