C++怎么实现收集雨水

引言

在计算机科学中，收集雨水问题是一个经典的算法问题。它通常用于考察程序员对数组、指针、动态规划等基本概念的理解和应用能力。本文将详细介绍如何使用C++实现收集雨水问题的解决方案，并通过多个示例代码和详细解释来帮助读者理解这一过程。

问题描述

收集雨水问题的描述如下：

给定一个非负整数数组，表示一个高度图，其中每个元素代表一个条形块的高度。计算在降雨后，这些条形块之间能够捕获多少雨水。

例如，给定数组 [0,1,0,2,1,0,1,3,2,1,2,1]，表示的高度图如下：

        *
    *   * *   *
*   * * * * * * *

在这个高度图中，* 表示条形块， 表示空位。降雨后，空位中会积攒雨水。我们需要计算这些雨水的总量。

解决思路

解决收集雨水问题的常见方法有以下几种：

1. 暴力法：对于每个条形块，找到其左边和右边的最高条形块，然后计算当前条形块能够捕获的雨水量。
2. 动态规划：预先计算每个条形块左边和右边的最高条形块，然后利用这些信息快速计算每个条形块能够捕获的雨水量。
3. 双指针法：使用两个指针从数组的两端向中间移动，逐步计算每个条形块能够捕获的雨水量。

本文将重点介绍动态规划和双指针法，并提供相应的C++实现代码。

动态规划法

算法思路

动态规划法的核心思想是预先计算每个条形块左边和右边的最高条形块，然后利用这些信息快速计算每个条形块能够捕获的雨水量。具体步骤如下：

1. 创建两个数组 left_max 和 right_max，分别用于存储每个条形块左边和右边的最高条形块高度。
2. 遍历数组，从左到右计算每个条形块的 left_max。
3. 遍历数组，从右到左计算每个条形块的 right_max。
4. 遍历数组，计算每个条形块能够捕获的雨水量，并累加到总雨水量中。

C++实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int trap(vector<int>& height) {
    if (height.empty()) return 0;

    int n = height.size();
    vector<int> left_max(n), right_max(n);

    // 计算每个条形块左边的最高条形块高度
    left_max[0] = height[0];
    for (int i = 1; i < n; ++i) {
        left_max[i] = max(left_max[i - 1], height[i]);
    }

    // 计算每个条形块右边的最高条形块高度
    right_max[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        right_max[i] = max(right_max[i + 1], height[i]);
    }

    // 计算总雨水量
    int water = 0;
    for (int i = 0; i < n; ++i) {
        water += min(left_max[i], right_max[i]) - height[i];
    }

    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "Total trapped water: " << trap(height) << endl;
    return 0;
}

代码解释

1. 初始化：首先检查数组是否为空，如果为空则直接返回0。
2. 计算 left_max：从左到右遍历数组，计算每个条形块左边的最高条形块高度，并存储在 left_max 数组中。
3. 计算 right_max：从右到左遍历数组，计算每个条形块右边的最高条形块高度，并存储在 right_max 数组中。
4. 计算雨水量：遍历数组，计算每个条形块能够捕获的雨水量，并累加到 water 变量中。
5. 返回结果：返回计算得到的总雨水量。

时间复杂度分析

• 计算 left_max 和 right_max 各需要一次遍历，时间复杂度为 O(n)。
• 计算雨水量需要一次遍历，时间复杂度为 O(n)。
• 总时间复杂度为 O(n)。

空间复杂度分析

• 需要两个额外的数组 left_max 和 right_max，空间复杂度为 O(n)。

双指针法

算法思路

双指针法的核心思想是使用两个指针从数组的两端向中间移动，逐步计算每个条形块能够捕获的雨水量。具体步骤如下：

1. 初始化两个指针 left 和 right，分别指向数组的起始和末尾。
2. 初始化两个变量 left_max 和 right_max，分别用于存储左边和右边的最高条形块高度。
3. 当 left 指针小于 right 指针时，执行以下步骤：
   • 如果 height[left] 小于 height[right]，则计算 left 指针处的雨水量，并移动 left 指针。
   • 否则，计算 right 指针处的雨水量，并移动 right 指针。
4. 返回计算得到的总雨水量。

C++实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int trap(vector<int>& height) {
    if (height.empty()) return 0;

    int left = 0, right = height.size() - 1;
    int left_max = height[left], right_max = height[right];
    int water = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            left_max = max(left_max, height[left]);
            water += left_max - height[left];
            ++left;
        } else {
            right_max = max(right_max, height[right]);
            water += right_max - height[right];
            --right;
        }
    }

    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "Total trapped water: " << trap(height) << endl;
    return 0;
}

代码解释

1. 初始化：首先检查数组是否为空，如果为空则直接返回0。
2. 初始化指针和变量：初始化 left 和 right 指针，以及 left_max 和 right_max 变量。
3. 计算雨水量：当 left 指针小于 right 指针时，根据 height[left] 和 height[right] 的大小关系，计算当前指针处的雨水量，并移动相应的指针。
4. 返回结果：返回计算得到的总雨水量。

时间复杂度分析

• 只需要一次遍历，时间复杂度为 O(n)。

空间复杂度分析

• 只需要常数级别的额外空间，空间复杂度为 O(1)。

示例分析

为了更好地理解上述算法的实现，我们将通过一个具体的示例来分析算法的执行过程。

示例数组

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

动态规划法执行过程

1. 计算 left_max：

   • left_max[0] = 0
   • left_max[1] = max(0, 1) = 1
   • left_max[2] = max(1, 0) = 1
   • left_max[3] = max(1, 2) = 2
   • left_max[4] = max(2, 1) = 2
   • left_max[5] = max(2, 0) = 2
   • left_max[6] = max(2, 1) = 2
   • left_max[7] = max(2, 3) = 3
   • left_max[8] = max(3, 2) = 3
   • left_max[9] = max(3, 1) = 3
   • left_max[10] = max(3, 2) = 3
   • left_max[11] = max(3, 1) = 3

2. 计算 right_max：

   • right_max[11] = 1
   • right_max[10] = max(1, 2) = 2
   • right_max[9] = max(2, 1) = 2
   • right_max[8] = max(2, 2) = 2
   • right_max[7] = max(2, 3) = 3
   • right_max[6] = max(3, 1) = 3
   • right_max[5] = max(3, 0) = 3
   • right_max[4] = max(3, 1) = 3
   • right_max[3] = max(3, 2) = 3
   • right_max[2] = max(3, 0) = 3
   • right_max[1] = max(3, 1) = 3
   • right_max[0] = max(3, 0) = 3

3. 计算雨水量：

   • water[0] = min(0, 3) - 0 = 0
   • water[1] = min(1, 3) - 1 = 0
   • water[2] = min(1, 3) - 0 = 1
   • water[3] = min(2, 3) - 2 = 0
   • water[4] = min(2, 3) - 1 = 1
   • water[5] = min(2, 3) - 0 = 2
   • water[6] = min(2, 3) - 1 = 1
   • water[7] = min(3, 3) - 3 = 0
   • water[8] = min(3, 2) - 2 = 0
   • water[9] = min(3, 2) - 1 = 1
   • water[10] = min(3, 2) - 2 = 0
   • water[11] = min(3, 1) - 1 = 0

4. 总雨水量：

   • water = 0 + 0 + 1 + 0 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 0 = 6

双指针法执行过程

1. 初始化：

   • left = 0, right = 11
   • left_max = 0, right_max = 1
   • water = 0

2. 第一次循环：

   • height[0] = 0 < height[11] = 1
   • left_max = max(0, 0) = 0
   • water += 0 - 0 = 0
   • left = 1

3. 第二次循环：

   • height[1] = 1 < height[11] = 1
   • left_max = max(0, 1) = 1
   • water += 1 - 1 = 0
   • left = 2

4. 第三次循环：

   • height[2] = 0 < height[11] = 1
   • left_max = max(1, 0) = 1
   • water += 1 - 0 = 1
   • left = 3

5. 第四次循环：

   • height[3] = 2 > height[11] = 1
   • right_max = max(1, 1) = 1
   • water += 1 - 1 = 0
   • right = 10

6. 第五次循环：

   • height[3] = 2 > height[10] = 2
   • right_max = max(1, 2) = 2
   • water += 2 - 2 = 0
   • right = 9

7. 第六次循环：

   • height[3] = 2 > height[9] = 1
   • right_max = max(2, 1) = 2
   • water += 2 - 1 = 1
   • right = 8

8. 第七次循环：

   • height[3] = 2 > height[8] = 2
   • right_max = max(2, 2) = 2
   • water += 2 - 2 = 0
   • right = 7

9. 第八次循环：

   • height[3] = 2 < height[7] = 3
   • left_max = max(1, 2) = 2
   • water += 2 - 2 = 0
   • left = 4

10. 第九次循环：

    • height[4] = 1 < height[7] = 3
    • left_max = max(2, 1) = 2
    • water += 2 - 1 = 1
    • left = 5

11. 第十次循环：

    • height[5] = 0 < height[7] = 3
    • left_max = max(2, 0) = 2
    • water += 2 - 0 = 2
    • left = 6

12. 第十一次循环：

    • height[6] = 1 < height[7] = 3
    • left_max = max(2, 1) = 2
    • water += 2 - 1 = 1
    • left = 7

13. 第十二次循环：

    • height[7] = 3 == height[7] = 3
    • 循环结束

14. 总雨水量：

    • water = 0 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 0 + 1 + 2 + 1 = 6

结论

通过上述分析和代码实现，我们可以看到，动态规划法和双指针法都能够有效地解决收集雨水问题。动态规划法通过预先计算每个条形块左边和右边的最高条形块高度，能够快速计算每个条形块能够捕获的雨水量。双指针法则通过从数组的两端向中间移动，逐步计算每个条形块能够捕获的雨水量，减少了空间复杂度。

在实际应用中，双指针法由于其较低的空间复杂度，通常更受青睐。然而，动态规划法由于其直观性和易于理解的特点，也是解决此类问题的常用方法。

希望本文能够帮助读者更好地理解收集雨水问题的解决方法，并能够在实际编程中灵活运用这些算法。