接雨水

 后端   大苹果   2024-08-08 18:15   735

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

 

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

 

提示:

  • n == height.length

  • 1 <= n <= 2 * 104

  • 0 <= height[i] <= 105

解法一:

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let left = 0;
    let right = height.length - 1;
    let sum = 0;
    let leftMax = 0;
    let rightMax = 0;
    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                sum += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                sum += rightMax - height[right];
            }
            right--;
        }
    }

    return sum;
};

说明:

要计算给定柱子高度图中的接雨水量,我们可以使用双指针的方法进行计算。这个问题通常被称为“接雨水问题”(Trapping Rain Water Problem)。

方法:双指针

算法步骤

  1. 初始化指针和变量

    • 左指针 left 指向数组的开始位置(索引 0)。

    • 右指针 right 指向数组的结束位置(索引 n-1)。

    • 初始化 left_max 和 right_max 分别为柱子高度的初始左端和右端。

    • 初始化 water_trapped 变量为 0,用于存储总的接雨水量。

  2. 遍历柱子高度数组

    • 如果 height[left] 小于等于 height[right]

    • 否则:

    • 如果 height[left] 大于等于 left_max,则更新 left_max

    • 否则,计算当前位置能接的水量为 left_max - height[left],并将该水量累加到 water_trapped

    • 移动左指针,即 left 增加 1。

    • 如果 height[right] 大于等于 right_max,则更新 right_max

    • 否则,计算当前位置能接的水量为 right_max - height[right],并将该水量累加到 water_trapped

    • 移动右指针,即 right 减少 1。

    • 当 left 小于 right 时,进行以下操作:

    • 返回结果

      • 当循环结束时,water_trapped 即为接雨水的总量。

    算法实现

    下面是用 Python 实现的代码:

    def trap(height):
        if not height:        
            return 0
     
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water_trapped = 0
     
        while left < right:        
            if height[left] <= height[right]:            
                if height[left] >= left_max:
                    left_max = height[left]            
                else:
                    water_trapped += left_max - height[left]
                left += 1
            else:            
                if height[right] >= right_max:
                    right_max = height[right]            
                else:
                    water_trapped += right_max - height[right]
                right -= 1
     
        return water_trapped
    # 示例
    height = [0,1,0,2,1,0,1,3,2,1,2,1]
    result = trap(height)
    print("能接的雨水总量:", result)

    示例

    • 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]

    • 输出:6

    解释

    在这个例子中,按照这种高度排列的柱子,经过雨水积累后,能够接住的雨水总量为 6

    复杂度分析

    • 时间复杂度:O(n),其中 n 是柱子高度数组的长度。我们只需遍历一次数组。

    • 空间复杂度:O(1),除了存储变量外,不需要额外的空间。

    这种方法有效地利用了双指针技巧,通过一次遍历即可完成对接雨水量的计算,是解决该问题的常用方法之一。