法算day7

[up主专用，视频内嵌代码贴在这]

接雨水

问题描述

给定 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

问题分析

这个问题的关键在于理解：每个位置能接的雨水量取决于它左右两边的最高柱子。

1. 对于每个位置，我们需要知道它左边的最高柱子和右边的最高柱子

2. 这两个最高柱子中较矮的那个决定了水位的高度

3. 水位高度减去当前位置的高度，就是这个位置能接的雨水量

这种方法的时间复杂度是O(n)，因为我们只需要遍历数组三次（计算左边最大值、右边最大值和计算总雨水量）。空间复杂度是O(n)，因为我们使用了两个辅助数组。

举例说明（动态规划法）

对于数组 [0,1,0,2,1,0,1,3,2,1,2,1]：

位置0：高度为0，左边最大值是0，右边最大值是3，能接的水量是min(0,3)-0=0
位置1：高度为1，左边最大值是1，右边最大值是3，能接的水量是min(1,3)-1=0
位置2：高度为0，左边最大值是1，右边最大值是3，能接的水量是min(1,3)-0=1
位置3：高度为2，左边最大值是2，右边最大值是3，能接的水量是min(2,3)-2=0
位置4：高度为1，左边最大值是2，右边最大值是3，能接的水量是min(2,3)-1=1
位置5：高度为0，左边最大值是2，右边最大值是3，能接的水量是min(2,3)-0=2
位置6：高度为1，左边最大值是2，右边最大值是3，能接的水量是min(2,3)-1=1
位置7：高度为3，左边最大值是3，右边最大值是3，能接的水量是min(3,3)-3=0
位置8：高度为2，左边最大值是3，右边最大值是2，能接的水量是min(2,3)-2=0
位置9：高度为1，左边最大值是3，右边最大值是2，能接的水量是min(2,3)-1=1
位置10：高度为2，左边最大值是3，右边最大值是2，能接的水量是min(2,3)-2=0
位置11：高度为1，左边最大值是3，右边最大值是1，能接的水量是min(3,1)-1=0

将所有位置的雨水量相加，就得到总雨水量6。

Java版（动态规划法）

// 时间复杂度：O(n)，空间复杂度：O(n)
int[] leftMax = new int[n];  // 创建左最大值数组，用于存储每个位置左侧的最大高度
int[] rightMax = new int[n]; // 创建右最大值数组，用于存储每个位置右侧的最大高度

// 预处理左最大值数组
// 从左到右遍历，计算每个位置左侧的最大高度
for (int i = 1; i < n; i++) {
    // leftMax[i] 等于前一个位置的左最大值和前一个柱子高度的较大值
    leftMax[i] = Math.max(leftMax[i-1], height[i-1]);
}

// 预处理右最大值数组
// 从右到左遍历，计算每个位置右侧的最大高度
for (int i = n-2; i >= 0; i--) {
    // rightMax[i] 等于后一个位置的右最大值和后一个柱子高度的较大值
    rightMax[i] = Math.max(rightMax[i+1], height[i+1]);
}

// 计算每个位置能接住的雨水量
for (int i = 0; i < n; i++) {
    // 当前位置能接住的雨水量由左右两侧最大高度的较小值决定
    int minHeight = Math.min(leftMax[i], rightMax[i]);
    // 只有当最小高度大于当前柱子高度时，才能接住雨水
    if (minHeight > height[i]) {
        // 雨水量 = 左右最大高度较小值 - 当前柱子高度
        water += minHeight - height[i];
    }
}

✅ 说明：

1. 时间复杂度：O(n)
2. 空间复杂度是 O(n)，需要额外的O(n)空间来存储左右最大高度数组

java版（方法一：双指针法）

public class TrapRainWater {
    public int trap(int[] height) {
        // 如果数组为空或长度小于3，无法接住雨水，直接返回0
        if (height == null || height.length < 3) {
            return 0;
        }
        
        int left = 0; // 左指针，从数组最左边开始
        int right = height.length - 1; // 右指针，从数组最右边开始
        int leftMax = 0; // 记录左边遇到的最大高度
        int rightMax = 0; // 记录右边遇到的最大高度
        int water = 0; // 记录总的接雨水量
        
        // 使用双指针法，从数组两端向中间遍历
        while (left < right) {
            // 如果左边的高度小于右边的高度
            if (height[left] < height[right]) {
                // 如果当前高度大于等于左边最大高度，更新左边最大高度
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    // 否则，当前位置可以接住雨水，水量为左边最大高度减去当前高度
                    water += leftMax - height[left];
                }
                // 左指针向右移动
                left++;
            } else {
                // 如果右边的高度小于等于左边的高度
                // 如果当前高度大于等于右边最大高度，更新右边最大高度
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    // 否则，当前位置可以接住雨水，水量为右边最大高度减去当前高度
                    water += rightMax - height[right];
                }
                // 右指针向左移动
                right--;
            }
        }
        
        return water;
    }
    
    // 测试代码
    public static void main(String[] args) {
        TrapRainWater solution = new TrapRainWater();
        
        // 示例1
        int[] height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(solution.trap(height1)); // 输出: 6
        
        // 示例2
        int[] height2 = {4,2,0,3,2,5};
        System.out.println(solution.trap(height2)); // 输出: 9
    }
}

✅ 说明：

1. 时间复杂度：O(n)
2. 空间复杂度是 O(1)

举例说明

对于数组 [0,1,0,2,1,0,1,3,2,1,2,1]：

0. 初始状态

   height = [0,1,0,2,1,0,1,3,2,1,2,1]
   索引:     0 1 2 3 4 5 6 7 8 9 10 11
   left = 0, right = 11
   leftMax = 0, rightMax = 0
   water = 0

1. 第1步：比较 height[0] 和 height[11]

   left=0, right=11
   height[0]=0, height[11]=1
   0 < 1 → 走if分支
   height[0]=0 >= leftMax=0? 是 → 更新leftMax=0
   left++ → left=1
   结果: leftMax=0, rightMax=0, water=0

2. 第2步：比较 height[1] 和 height[11]

   left=1, right=11
   height[1]=1, height[11]=1
   1 >= 1 → 走else分支
   height[11]=1 >= rightMax=0? 是 → 更新rightMax=1
   right-- → right=10
   结果: leftMax=0, rightMax=1, water=0

3. 第3步：比较 height[1] 和 height[10]

   left=1, right=10
   height[1]=1, height[10]=2
   1 < 2 → 走if分支
   height[1]=1 >= leftMax=0? 是 → 更新leftMax=1
   left++ → left=2
   结果: leftMax=1, rightMax=1, water=0

4. 第4步：比较 height[2] 和 height[10]

   left=2, right=10
   height[2]=0, height[10]=2
   0 < 2 → 走if分支
   height[2]=0 >= leftMax=1? 否 → water += 1-0=1
   left++ → left=3
   结果: leftMax=1, rightMax=1, water=1

5. 第5步：比较 height[3] 和 height[10]

   left=3, right=10
   height[3]=2, height[10]=2
   2 >= 2 → 走else分支
   height[10]=2 >= rightMax=1? 是 → 更新rightMax=2
   right-- → right=9
   结果: leftMax=1, rightMax=2, water=1

6. 第6步：比较 height[3] 和 height[9]

   left=3, right=9
   height[3]=2, height[9]=1
   2 >= 1 → 走else分支
   height[9]=1 >= rightMax=2? 否 → water += 2-1=1
   right-- → right=8
   结果: leftMax=1, rightMax=2, water=2

7. 第7步：比较 height[3] 和 height[8

   left=3, right=8
   height[3]=2, height[8]=2
   2 >= 2 → 走else分支
   height[8]=2 >= rightMax=2? 是 → 更新rightMax=2
   right-- → right=7
   结果: leftMax=1, rightMax=2, water=2

8. 第8步：比较 height[3] 和 height[7]

   left=3, right=7
   height[3]=2, height[7]=3
   2 < 3 → 走if分支
   height[3]=2 >= leftMax=1? 是 → 更新leftMax=2
   left++ → left=4
   结果: leftMax=2, rightMax=2, water=2

9. 第9步：比较 height[4] 和 height[7]

   left=4, right=7
   height[4]=1, height[7]=3
   1 < 3 → 走if分支
   height[4]=1 >= leftMax=2? 否 → water += 2-1=1
   left++ → left=5
   结果: leftMax=2, rightMax=2, water=3

10. 第10步：比较 height[5] 和 height[7]

    left=5, right=7
    height[5]=0, height[7]=3
    0 < 3 → 走if分支
    height[5]=0 >= leftMax=2? 否 → water += 2-0=2
    left++ → left=6
    结果: leftMax=2, rightMax=2, water=5

11. 第11步：比较 height[6] 和 height[7]

    left=6, right=7
    height[6]=1, height[7]=3
    1 < 3 → 走if分支
    height[6]=1 >= leftMax=2? 否 → water += 2-1=1
    left++ → left=7
    结果: leftMax=2, rightMax=2, water=6

12. 第12步：left=7, right=7

    left >= right → 循环结束
    最终结果: water = 6

python版（双指针法）

def trap(height):
    """
    计算接雨水的总量
    使用双指针法，从数组的两端向中间移动
    """
    # 如果数组为空或长度小于3，无法接住雨水，直接返回0
    if not height or len(height) < 3:
        return 0
    
    # 初始化左右指针
    left = 0
    right = len(height) - 1
    
    # 记录左右两边的最大高度
    left_max = 0
    right_max = 0
    
    # 记录总雨水量
    water = 0
    
    # 当左指针小于右指针时循环
    while left < right:
        # 如果左边的高度小于右边的高度
        if height[left] < height[right]:
            # 如果当前左边高度大于等于左边最大高度
            if height[left] >= left_max:
                # 更新左边最大高度
                left_max = height[left]
            else:
                # 计算当前位置能接的雨水量并累加
                # 雨水量 = 左边最大高度 - 当前高度
                water += left_max - height[left]
            # 左指针右移
            left += 1
        else:
            # 如果当前右边高度大于等于右边最大高度
            if height[right] >= right_max:
                # 更新右边最大高度
                right_max = height[right]
            else:
                # 计算当前位置能接的雨水量并累加
                # 雨水量 = 右边最大高度 - 当前高度
                water += right_max - height[right]
            # 右指针左移
            right -= 1
    
    return water

# 测试代码
if __name__ == "__main__":
    # 示例1
    height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
    print(trap(height1))  # 输出: 6
    
    # 示例2
    height2 = [4,2,0,3,2,5]
    print(trap(height2))  # 输出: 9