当前位置：首页 > news >正文

【LeetCode 热题 100】42. 接雨水——（解法一）前后缀分解

news 2025/6/30 3:47:57

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)。