字节高频编程考题：接雨水 （困难）

字节高频编程考题：接雨水 （困难）

引用

CSDN

1.

https://m.blog.csdn.net/ZWL53223456789/article/details/142680753

题目描述

给定 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 *
• 0 <= height[i] <=

解题思路

为了计算在柱子之间能够接住多少雨水，可以使用双指针的方法。具体步骤如下：

1. 初始化指针和变量：使用两个指针 left 和 right 分别指向数组的两端。leftMax 和 rightMax 分别记录从左侧到 left 位置的最大高度和从右侧到 right 位置的最大高度。water 用于记录接住的总雨水量。

2. 双指针遍历：如果 height[left] 小于 height[right] ，则说明 left 位置的柱子可能会接住雨水，接住的水量取决于 leftMax 和当前 height[left] 的差值。如果 leftMax 大于 height[left] ，则能接住雨水，并将 left 指针右移。否则，移动 right 指针并以同样的方式计算 right 位置能接住的雨水量。

3. 更新最大高度：每次移动指针时，更新 leftMax 或 rightMax ，以便在接下来的计算中使用。

4. 终止条件：当 left 和 right 指针相遇时，遍历结束，所有的雨水量已经计算完毕。

复杂度分析

• 时间复杂度：O(n)。双指针遍历整个数组一次，因此时间复杂度为 O(n)，其中 n 是数组的长度。

• 空间复杂度：O(1)。只使用了固定的额外空间来存储指针和变量，因此空间复杂度为 O(1)。

代码实现

package org.zyf.javabasic.letcode.hot100.twopoint;
/**
 * @program: zyfboot-javabasic
 * @description: 接雨水 
 * @author: zhangyanfeng
 * @create: 2024-08-21 21:09
 **/
public class TrapSolution {
    public int trap(int[] height) {
        // 初始化双指针，分别指向数组的两端
        int left = 0, right = height.length - 1;
        // 初始化左边和右边的最大高度
        int leftMax = 0, rightMax = 0;
        // 初始化接住的雨水量
        int water = 0;
        // 当左指针小于右指针时，继续遍历
        while (left < right) {
            // 如果左边柱子低于右边柱子，处理左边
            if (height[left] < height[right]) {
                // 如果当前左边的高度大于等于 leftMax，更新 leftMax
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    // 否则，leftMax 大于当前高度，计算能接住的水量
                    water += leftMax - height[left];
                }
                // 将左指针右移
                left++;
            } else {
                // 如果右边柱子低于或等于左边柱子，处理右边
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    // 否则，rightMax 大于当前高度，计算能接住的水量
                    water += rightMax - height[right];
                }
                // 将右指针左移
                right--;
            }
        }
        // 返回总的接住的雨水量
        return water;
    }
    public static void main(String[] args) {
        TrapSolution solution = new TrapSolution();
        // 测试用例 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
    }
}

具体可参考：https://zyfcodes.blog.csdn.net/article/details/141401712