Problem: 42. 接雨水
整体思路
这段代码旨在解决经典的“接雨水”问题。给定一个非负整数数组，数组中的每个元素代表一个柱子的高度，柱子的宽度默认为1。目标是计算这些柱子之间能够 trapping（接住）多少单位的雨水。
代码的整体思路可以概括为以下几个步骤：
理解接水原理：
对于数组中的任何一个位置i（代表一个柱子），它上方能接的雨水的高度取决于其左边所有柱子中的最高者（left_max）和其右边所有柱子中的最高者（right_max）。具体来说，水位高度将是min(left_max, right_max)。如果这个水位高于当前柱子height[i]的高度，那么在位置i上就能接到雨水，接到的雨水量为min(left_max, right_max) - height[i]。如果水位不高于当前柱子，则当前位置接不到雨水。预计算左右最大高度：
为了高效地获取每个位置的left_max和right_max，代码采用了预计算的方式：preMax数组：preMax[i]存储从数组开头（索引0）到当前位置i（包括i）的所有柱子中的最大高度。这个数组可以通过一次从左到右的遍历来填充：preMax[i] = max(preMax[i-1], height[i])。sufMax数组：sufMax[i]存储从当前位置i（包括i）到数组末尾（索引n-1）的所有柱子中的最大高度。这个数组可以通过一次从右到左的遍历来填充：sufMax[i] = max(sufMax[i+1], height[i])。
计算总接水量：
在preMax和sufMax数组都计算完毕后，再次遍历原始的height数组。对于每个位置i：- 确定该位置的水位：
waterLevel = min(preMax[i], sufMax[i])。 - 计算该位置接到的雨水量：
trappedWaterAt_i = waterLevel - height[i]。由于preMax[i]和sufMax[i]至少不小于height[i]（因为它们在计算时都考虑了height[i]本身），所以waterLevel - height[i]的结果必然是非负的。如果height[i]本身就是左右最高点之一，则差值为0，表示此处不存水（或水面与柱顶齐平）。 - 将每个位置计算得到的雨水量累加到总接水量
ans中。
- 确定该位置的水位：
返回结果：
遍历完成后，ans中存储的就是总的接雨水量，将其返回。
核心数据结构的选择：
height(输入)：一维整型数组，表示柱子的高度。preMax：一维整型数组，用于存储前缀最大值。sufMax：一维整型数组，用于存储后缀最大值。
关键的判断或循环逻辑：
- 第一个循环（同时计算
preMax和sufMax）：preMax从左到右计算，依赖前一个preMax值和当前height。sufMax从右到左计算，依赖后一个sufMax值和当前height。- 代码巧妙地在一个循环中通过两个索引
i（递增）和j（递减）来同时填充这两个数组，优化了常数时间（但不是复杂度级别）。
- 第二个循环（计算总雨水量）：遍历每个柱子，利用预计算好的
preMax[i]和sufMax[i]来确定水位，并计算当前柱子上方能接的雨水。
这种方法通过两次预处理遍历（或者一次特殊遍历）和一次计算遍历，总共三次（或等效于两次完整遍历）线性扫描数组来解决问题。
完整代码
class Solution {
public int trap(int[] height) {
int n = height.length; // 获取柱子数组的长度
// preMax[i] 存储从索引 0 到 i 的柱子中的最大高度（左侧最高点，包含当前点）
int[] preMax = new int[n];
// sufMax[i] 存储从索引 i 到 n-1 的柱子中的最大高度（右侧最高点，包含当前点）
int[] sufMax = new int[n];
int ans = 0; // 初始化总接水量
// 初始化 preMax 数组的第一个元素
// 第一个柱子左边的最高点（含自身）就是它自己的高度
preMax[0] = height[0];
// 初始化 sufMax 数组的最后一个元素
// 最后一个柱子右边的最高点（含自身）就是它自己的高度
sufMax[n - 1] = height[n - 1];
// 使用一个循环同时计算 preMax 和 sufMax 数组的其余部分
// i 从左向右遍历（用于 preMax），从索引 1 开始
// j 从右向左遍历（用于 sufMax），从索引 n-2 开始
// 循环条件 i < n 确保 i 不会越界，并且 preMax 数组会被完全填充
// j-- 确保 sufMax 数组从右向左被填充
for (int i = 1, j = n - 2; i < n; i++, j--) {
// preMax[i] 是前一个位置的 preMax 和当前高度 height[i] 中的较大值
preMax[i] = Math.max(preMax[i - 1], height[i]);
// sufMax[j] 是后一个位置的 sufMax 和当前高度 height[j] 中的较大值
sufMax[j] = Math.max(sufMax[j + 1], height[j]);
}
// 遍历所有柱子，计算每个柱子上方能接的雨水量
for (int i = 0; i < n; i++) {
// 对于当前柱子 i，其能形成的水位高度取决于其左侧最高 preMax[i] 和右侧最高 sufMax[i] 中的较小者
int waterLevel = Math.min(preMax[i], sufMax[i]);
// 当前柱子 i 上方能接的雨水量 = 水位高度 - 当前柱子高度
// 因为 waterLevel >= height[i] （由于 preMax[i] 和 sufMax[i] 在计算时都包含了 height[i]），
// 所以 (waterLevel - height[i]) 总是非负的。
ans += waterLevel - height[i];
}
return ans; // 返回计算得到的总接水量
}
}
时空复杂度
时间复杂度：
int n = height.length;: O(1)int[] preMax = new int[n]; int[] sufMax = new int[n];: O(N) - 创建两个大小为 N 的数组。分配内存通常认为是 O(N) 操作，或者至少与N相关。preMax[0] = height[0]; sufMax[n - 1] = height[n - 1];: O(1) - 两个赋值操作。- 第一个
for循环 (for (int i = 1, j = n - 2; i < n; i++, j--)):- 这个循环从
i = 1开始，到i = n - 1结束（当i = n时，i < n为 false）。 - 因此，循环体执行
n - 1次。 - 循环体内部的操作 (
Math.max, 数组访问，赋值) 都是 O(1) 的。 - 所以，这个循环的总时间复杂度是 O(N)。
- 这个循环从
- 第二个
for循环 (for (int i = 0; i < n; i++)):- 这个循环从
i = 0开始，到i = n - 1结束。 - 循环体执行
n次。 - 循环体内部的操作 (
Math.min, 数组访问，减法，加法赋值) 都是 O(1) 的。 - 所以，这个循环的总时间复杂度是 O(N)。
- 这个循环从
综合来看，主要的时间消耗来自于两个独立的线性扫描（或者一个合并的线性扫描预处理）和另一个线性扫描计算结果。因此，总的时间复杂度是 O(N) + O(N) = O(N)。
最终时间复杂度: O(N)
空间复杂度：
int[] preMax = new int[n];: 额外使用了大小为 N 的整型数组，空间 O(N)。int[] sufMax = new int[n];: 额外使用了大小为 N 的整型数组，空间 O(N)。ans,n,i,j: 这些是基本类型的变量，占用 O(1) 的空间。- 输入数组
height不计入额外空间复杂度，因为它是输入数据。
额外使用的主要空间是 preMax 和 sufMax 数组。
因此，总的额外空间复杂度是 O(N) + O(N) + O(1) = O(N)。
最终空间复杂度: O(N)
参考灵茶山艾府