LeetCode题练习与总结：接雨水

一、题目

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

二、解题思路

这个问题可以通过双指针或者暴力解法来解决。我们的目标是计算在每个低洼地带能够存储的雨水量。雨水的存储量取决于它两侧的最高柱子和当前柱子的高度。以下是解决这个问题的步骤：

遍历数组，找到两侧的最高柱子（可以使用双指针，一个从左边开始向右移动，另一个从右边向左移动）。
对于每个位置，其能够存储的雨水量取决于它两侧最高柱子中较低的一个和当前位置的柱子高度。
将每个位置能够存储的雨水量累加起来，即为最终的雨水总量。

三、具体代码

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int n = height.length;
        int leftMax[] = new int[n];
        int rightMax[] = new int[n];
        int trappedWater = 0;

        // 初始化左右两侧的最大高度数组
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 计算每个位置的雨水量并累加
        for (int i = 0; i < n; i++) {
            trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return trappedWater;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化leftMax数组需要一次遍历，时间复杂度为O(n)。
初始化rightMax数组需要一次遍历，时间复杂度为O(n)。
计算每个位置的雨水量并累加的过程也是一次遍历，时间复杂度为O(n)。
因此，总的时间复杂度是这三个步骤时间复杂度的和，即O(n) + O(n) + O(n) = O(n)。

2. 空间复杂度

leftMax数组和rightMax数组各占用O(n)的空间。
trappedWater变量占用常数空间。
所以，总的空间复杂度是O(n)，因为两个数组的空间占用是主要的。

五、总结知识点

数组处理：代码处理了一个整数数组height，这个数组代表了每个柱子的高度。数组是编程中常用的数据结构，用于存储一系列元素。
边界检查：在进行数组操作之前，代码首先检查了数组是否为空或者长度为0，这是为了避免在数组操作中出现NullPointerException或数组越界的错误。
双指针/双端扫描：代码使用了两个数组leftMax和rightMax来分别从左到右和从右到左记录已访问过的最高柱子高度。这种从两端向中间扫描的方法是一种常见的双指针技巧。
最大值更新：在填充leftMax和rightMax数组时，代码使用了Math.max函数来更新和记录每一步遇到的最大值。这是处理此类问题的关键步骤，需要知道如何更新和维护局部最大值。
条件运算：在计算雨水量时，使用了Math.min函数来确定每个位置的雨水量，这是因为雨水量受到两侧最高柱子中较低的一个限制。
累加求和：通过遍历数组并累加每个位置的雨水量，得到了总的雨水量。这是简单的循环和累加操作，是编程基础中常见的求和方法。