【LeetCode 面试经典150题】42. Trapping Rain Water 接雨水

42. Trapping Rain Water

题目大意

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

中文释义

给定 n 个非负整数，代表以宽度为 1 的条形图的高程图，计算下雨后它能接多少雨水。

Example

Example 1:

• Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
• Output: 6
• Explanation: 上述高程图（黑色部分）由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示。在这种情况下，被接的雨水量（蓝色部分）为 6 单位。

Example 2:

• Input: height = [4,2,0,3,2,5]
• Output: 9

Constraints

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

解题思路

算法描述

• 这段代码的目的是计算在一个给定的高程图中能够接多少雨水。

• 第i个位置能接多少雨水，取决于 i 位置左边最大的元素 和 i 位置右边最大的元素。

• 设置 left[i] 数组记录 i 位置左边最大元素。

• 设置 right[i] 数组记录 i 位置右边最大元素。

• i 位置接水量 = min(left[i], right[i]) - height[i]

算法的关键步骤如下：

1. 初始化两个辅助数组:

   • 创建两个数组 left 和 right，分别用于存储每个位置左侧和右侧的最高高度。
   • 初始化 left[0] 和 right[size - 1] 为 -1，表示最左端和最右端没有高程。

2. 从左至右计算最高高程:

   • 遍历数组 height，从左到右填充 left 数组。
   • 对于每个位置 i，left[i] 存储 i 左侧的最高高程。

3. 从右至左计算最高高程:

   • 反向遍历数组 height，从右到左填充 right 数组。
   • 对于每个位置 j，right[j] 存储 j 右侧的最高高程。

4. 计算接雨水量:

   • 遍历数组 height，从第二个位置到倒数第二个位置。
   • 计算每个位置能接的雨水量，等于 min(left[i], right[i]) - height[i]。
   • 如果计算结果大于0，累加到 sum。

5. 返回结果:

   • 最后返回累加的雨水量 sum。

代码实现

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