chatgpt接雨水

接雨水.md

题目描述： 给定一个非负整数数组 height 表示一系列柱子的高度，每个柱子的宽度为 1。计算下雨后，能够在这些柱子之间存储多少雨水。

例子：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：如下图所示，灰色区域表示可以存储雨水的地方，可以存储的雨水量为 6 个单位。

   |
   |
   |       1
   |   1███1
   | 1██████1
   |█████████
   |█████████
   |█████████

要求：

• 只能计算连续的柱子之间可以存储的雨水，不能计算柱子之间的间隔。
• 可以假设数组的两端都被无限高的墙壁包围，且数组中的柱子高度都大于等于 0。 接雨水问题是一个经典的算法问题，可以使用双指针的方法来解决。具体步骤如下：

1. 定义两个指针，left和right，分别指向数组的首尾。
2. 定义两个变量，leftMax和rightMax，分别表示左侧和右侧的最大高度。初始时，将leftMax和rightMax都设置为0。
3. 定义一个变量，result，表示最终接到的雨水量。初始时，将result设置为0。
4. 进行双指针遍历，直到left和right相遇。
   • 如果height[left] < height[right]，则说明当前left位置的高度较低，可以接到雨水。
     • 如果height[left] > leftMax，更新leftMax为height[left]。
     • 否则，将result增加leftMax - height[left]，表示接到的雨水量。
     • 将left指针右移一位。
   • 如果height[left] >= height[right]，则说明当前right位置的高度较低，可以接到雨水。
     • 如果height[right] > rightMax，更新rightMax为height[right]。
     • 否则，将result增加rightMax - height[right]，表示接到的雨水量。
     • 将right指针左移一位。
5. 返回result，表示最终接到的雨水量。

下面是使用C++实现的代码：

int trap(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int leftMax = 0;
    int rightMax = 0;
    int result = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > leftMax) {
                leftMax = height[left];
            } else {
                result += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] > rightMax) {
                rightMax = height[right];
            } else {
                result += rightMax - height[right];
            }
            right--;
        }
    }
    
    return result;
}

使用示例：

vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
cout << trap(height) << endl;  // 输出 6

希望对你有帮助！