1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution
{
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        if (n == 0) return 0; // 边界条件，空数组返回 0

        // 1. 构建左侧最高高度数组
        std::vector<int> left_max(n);
        left_max[0] = height[0];
        for (int i = 1; i < n; ++i)
            left_max[i] = std::max(left_max[i - 1], height[i]);

        // 2. 构建右侧最高高度数组
        std::vector<int> right_max(n);
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i)
            right_max[i] = std::max(right_max[i + 1], height[i]);

        // 3. 计算总雨水量
        int res = 0;
        for (int i = 0; i < n; ++i)
            res += std::min(left_max[i], right_max[i]) - height[i];

        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def trap(self, height: List[int]) -> int:
      n = len(height)

      left_max_height = [0] * n
      left_max_height[0] = height[0]
      for i in range(1, n):
        left_max_height[i] = max(left_max_height[i - 1], height[i])

      right_max_height = [0] * n
      right_max_height[n - 1] = height[n - 1]

      for i in range(n - 2, -1, -1):
        right_max_height[i] = max(right_max_height[i + 1], height[i])

      rainfall = 0
      for i in range(n):
        rainfall += min(left_max_height[i], right_max_height[i]) - height[i]

      return rainfall

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

func trap(height []int) int {
  n := len(height)

  left_max_height := make([]int, n)
  left_max_height[0] = height[0]
  for i := 1; i < n; i ++ {
    if left_max_height[i - 1] < height[i] {
      left_max_height[i] = height[i]
    } else {
      left_max_height[i] = left_max_height[i - 1]
    }
  }

  right_max_height := make([]int, n)
  right_max_height[n - 1] = height[n - 1]
  for i := n - 2; i >= 0; i -- {
    if right_max_height[i + 1] < height[i] {
      right_max_height[i] = height[i]
    } else {
      right_max_height[i] = right_max_height[i + 1]
    }
  }

  rainfall := 0
  for i := 0; i < n; i ++ {
    if left_max_height[i] < right_max_height[i] {
      rainfall += left_max_height[i] - height[i]
    } else {
      rainfall += right_max_height[i] - height[i]
    }
  }

  return rainfall
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

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

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

  let rainfall = 0;
  for (let i = 0; i < n; ++i) {
    rainfall += Math.min(left_max_height[i], right_max_height[i]) - height[i];
  }

  return rainfall;
};