接雨水
· 阅读需 11 分钟
力扣面试经典——42题
💡 参考代码：
/**
* @brief 计算柱状图中能够接住的雨水总量
*
* 使用双指针法解决接雨水问题。对于每个位置，能接住的雨水量取决于其左侧和右侧的最大高度中的较小值。
* 通过维护两个指针和对应的左右侧最大高度，从两端向中间遍历，累计可接雨水量。
*
* @param height 柱子高度数组，每个元素代表一个宽度为1的柱子的高度
* @param heightSize 数组长度，表示柱子的数量
* @return int 返回能够接住的雨水总量
*
* @example
* 输入: height = [0,1,0,2,1,0,1,3,2,1,2,1], heightSize = 12
* 输出: 6
*
* @example
* 输入: height = [4,2,0,3,2,5], heightSize = 6
* 输出: 9
*
* @complexity
* 时间复杂度: O(n) - 只需要遍历一次数组
* 空间复杂度: O(1) - 只使用了常数级别的额外空间
*/
int trap(int* height, int heightSize) {
// 柱子数量少于3个时无法接住雨水
if (heightSize <= 2) return 0;
int left = 0; // 左指针，从数组起始位置开始
int right = heightSize - 1; // 右指针，从数组末尾位置开始
int leftMax = 0; // 记录左侧遍历过程中的最大高度
int rightMax = 0; // 记录右侧遍历过程中的最大高度
int result = 0; // 累计接住的雨水总量
// 双指针向中间移动，直到相遇
while (left < right) {
// 当左侧柱子高度小于右侧柱子高度时，处理左侧
if (height[left] < height[right]) {
// 如果当前柱子高度大于等于左侧最大高度，说明此位置接不到雨水
if (height[left] >= leftMax) {
leftMax = height[left];//更新左侧最大高度
} else {
// 否则可以接住雨水，累加到结果中
result += leftMax - height[left];
}
left++; // 左指针右移
} else {
// 当右侧柱子高度小于等于左侧柱子高度时，处理右侧
// 如果当前柱子高度大于等于右侧最大高度，说明此位置接不到雨水
if (height[right] >= rightMax) {
rightMax = height[right];//更新右侧最大高度
} else {
// 否则可以接住雨水，累加到结果中
result += rightMax - height[right];
}
right--; // 右指针左移
}
}
return result; // 返回接住的雨水总量
}
📖 总结：
点击展开题目总结
🤔 接雨水
1️⃣ 题目核心信息
🎯 功能描述：给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子下雨之后能接多少雨水。
📥 输入输出：
- 输入：
height- 柱子高度数组，每个元素代表一个宽度为1的柱子的高度；heightSize- 数组长度 - 输出：返回能够接住的雨水总量（整数）
2️⃣ 实现原理
💡 核心思路：使用双指针法，从数组两端向中间遍历，通过维护左右两侧的最大高度来计算每个位置能够接住的雨水量。
📋 实现步骤：
- 初始化左右指针分别指向数组首尾，同时维护左侧最大高度和右侧最大高度
- 比较左右指针所指元素的大小，选择较小的一侧进行处理
- 如果当前元素大于等于该侧最大高度，则更新最大高度
- 如果当前元素小于该侧最大高度，则累加可接雨水量（最大高度减去当前高度）
- 移动处理过的指针，重复步骤2-4直到左右指针相遇
3️⃣ 关键点解析
🎯 代码技巧
- 使用双指针从两端向中间逼近，减少空间复杂度
- 利用"短板效应"思想，总是处理较矮一侧的柱子
- 通过维护单侧最大值避免了预处理整个数组的需要
- 巧妙利用高度比较结果决定处理方向
4️⃣ 使用场景
✅ 适用情况：
- 需要计算地形中能够存储的水量
- 处理类似"容器盛水"的几何问题
- 需要在数组中寻找"凹陷"区域的累积值
⚠️ 前提条件：
- 输入数组元素为非负整数
- 数组长度至少为3才能接住雨水
- 每个柱子宽度固定为1
5️⃣ 复杂度分析
-
⏱️ 时间复杂度：O(n) - 只需要遍历一次数组，每个元素最多被访问一次
-
💾 空间复杂度：O(1) - 只使用了常数级别的额外空间，不依赖数组大小
6️⃣ 注意事项
🚩 边界情况：
- 数组长度小于3时无法接住雨水，直接返回0
- 数组为空或为NULL的情况
- 所有柱子高度相同的情况
💥 易错点：
- 混淆左右最大高度的更新条件，应该是大于等于时更新
- 忘记在处理完一个位置后移动指针
- 错误地在两侧高度相等时的处理逻辑
- 没有正确理解雨水量计算公式：min(leftMax, rightMax) - currentHeight
7️⃣ 补充解释
正确的理解方式 让我用一个简单的例子来说明：
索引: 0 1 2 3 4 5 6
高度: 2 0 1 0 0 1 3
L * R
对于位置 * (索引3)，它的"两侧"是指：
- 左侧：
height[0],height[1],height[2]中的最大值 = max(2,0,1) = 2 - 右侧：
height[4],height[5],height[6]中的最大值 = max(0,1,3) = 3 所以位置3能接的雨水 = min(2,3) - 0 = 2
为什么比较height[0]和height[11]？
在双指针法中，我们比较 height[left] 和 height[right] 并不是为了计算这两个位置的雨水，而是为了确定处理方向。
这背后的逻辑是：
-
如果
height[left]<height[right]，那么我们可以确定左侧指针指向的位置的雨水量只由左侧最大值决定 -
这是因为右边有一个更高的墙，水面高度至少能达到左边的最大值
举个更直观的例子
索引: 0 1 2 3 4 5 6 7
高度: 3 0 0 0 0 0 0 5
L R
当我们比较 height[0]=3 和 height[7]=5 时：
-
因为 3 < 5，所以我们处理左侧位置(索引0)
-
但索引0是边界，不能接雨水
-
然后 left++，继续处理索引1的位置 对于索引1的位置：
-
它左边的最大值是3
-
它右边的最大值是5(注意：是整个右边的最大值，不只是相邻的)
-
所以它能接的雨水 = min(3,5) - 0 = 3
总结
-
"两侧"指的是当前位置左边所有柱子中的最大值和右边所有柱子中的最大值
-
比较 height[left] 和 height[right] 是为了决定处理策略，而不是计算这两个位置的雨水
-
这是一个巧妙的优化，避免了需要预计算每个位置左右两侧最大值的步骤
有点懂了，但没完全懂⬇️
我理解的 左侧、右侧 这里的左右侧并不是指某个位置的左右侧，而是左右侧的指针（即上面定义的 left 和 right），比如刚开始时 height[left] < height[right] 的
话，表明此刻应该处理左侧指针指向的位置（而并非该位置的左侧）。如果该位置的值 height[left] = 2 ,leftMax = 1 ,即此刻该位置无法接到雨水，像下面这样：
|⬅️//右侧这里相当有无形的“墙”，高度至少是 height[right]
█ | //真正决定能够接多少雨水的是 leftMax
█ █ | //此处 leftMax 过小，可见无法接到雨水，于是要更新 leftMax = height[left]
8️⃣ 更多解法
以下两种解法，我尚不理解，但也补充上，供日后参考、研究。
动态规划
/**
* @brief 计算柱状图中能够接住的雨水总量
*
* 使用动态规划方法解决接雨水问题。通过预计算每个位置左侧和右侧的最大高度，
* 然后根据"短板效应"计算每个位置能够接住的雨水量。
*
* 核心公式：每个位置能接住的雨水量 = min(左侧最大高度, 右侧最大高度) - 当前位置高度
*
* @param height 柱子高度数组，每个元素代表一个宽度为1的柱子的高度
* @param heightSize 数组长度，表示柱子的数量
* @return int 返回能够接住的雨水总量
*
* @example
* 输入: height = [0,1,0,2,1,0,1,3,2,1,2,1], heightSize = 12
* 输出: 6
*
* @example
* 输入: height = [4,2,0,3,2,5], heightSize = 6
* 输出: 9
*
* @complexity
* 时间复杂度: O(n) - 需要遍历数组三次
* 空间复杂度: O(n) - 需要额外的两个数组存储左侧和右侧最大高度
*/
int trap(int* height, int heightSize) {
// 边界条件：柱子数量少于3个时无法接住雨水
if (heightSize <= 2) return 0;
// 分配内存存储每个位置左侧的最大高度
int* leftMax = (int*)malloc(sizeof(int) * heightSize);
// 初始化第一个位置的左侧最大高度为自身
leftMax[0] = height[0];
// 从左到右遍历，计算每个位置左侧的最大高度
// leftMax[i] 表示 height[0..i] 中的最大值
for (int i = 1; i < heightSize; i++) {
leftMax[i] = (leftMax[i - 1] > height[i]) ? leftMax[i - 1] : height[i];
}
// 分配内存存储每个位置右侧的最大高度
int* rightMax = (int*)malloc(sizeof(int) * heightSize);
// 初始化最后一个位置的右侧最大高度为自身
rightMax[heightSize - 1] = height[heightSize - 1];
// 从右到左遍历，计算每个位置右侧的最大高度
// rightMax[i] 表示 height[i..heightSize-1] 中的最大值
for (int i = heightSize - 2; i >= 0; i--) {
rightMax[i] = (rightMax[i + 1] > height[i]) ? rightMax[i + 1] : height[i];
}
// 计算总的雨水量
int result = 0;
// 遍历每个位置，计算该位置能接住的雨水量
for (int i = 0; i < heightSize; i++) {
// 根据"短板效应"，水面高度由两侧最大高度的较小值决定
int minHeight = (leftMax[i] < rightMax[i]) ? leftMax[i] : rightMax[i];
// 只有当水面高度大于当前位置高度时才能接住雨水
if (minHeight > height[i]) {
// 累加该位置的雨水量
result += minHeight - height[i];
}
}
// 释放动态分配的内存
free(leftMax);
free(rightMax);
// 返回接住的雨水总量
return result;
}
单调栈
/**
* @brief 计算柱状图中能够接住的雨水总量
*
* 使用单调栈方法解决接雨水问题。通过维护一个单调递减的栈来追踪可能形成凹陷的柱子，
* 当遇到较高的柱子时，计算由当前柱子、栈顶柱子和栈中下一个柱子形成的凹陷区域的雨水量。
*
* @param height 柱子高度数组，每个元素代表一个宽度为1的柱子的高度
* @param heightSize 数组长度，表示柱子的数量
* @return int 返回能够接住的雨水总量
*
* @example
* 输入: height = [0,1,0,2,1,0,1,3,2,1,2,1], heightSize = 12
* 输出: 6
*
* @example
* 输入: height = [4,2,0,3,2,5], heightSize = 6
* 输出: 9
*
* @complexity
* 时间复杂度: O(n) - 每个元素最多入栈和出栈一次
* 空间复杂度: O(n) - 最坏情况下栈中存储所有元素
*/
int trap(int* height, int heightSize) {
// 边界条件：柱子数量少于3个时无法接住雨水
if (heightSize <= 2) return 0;
// 创建栈用于存储柱子的索引
int* stack = (int*)malloc(sizeof(int) * heightSize);
int top = -1; // 栈顶指针，-1表示空栈
int result = 0; // 累计接住的雨水总量
// 从左到右遍历每个柱子
for (int i = 0; i < heightSize; i++) {
// 当栈不为空且当前柱子高度大于栈顶柱子高度时
while (top >= 0 && height[i] > height[stack[top]]) {
// 弹出栈顶元素作为凹陷的底部
int bottom = stack[top--];
// 如果栈为空，说明没有左边界，无法形成凹陷
if (top < 0) break;
// 计算凹陷区域的水平距离（宽度）
// 距离 = 右边界索引 - 左边界索引 - 1
int distance = i - stack[top] - 1;
// 计算凹陷区域的高度
// 高度 = min(左边界高度, 右边界高度) - 底部高度
int boundedHeight = (height[i] < height[stack[top]] ? height[i] : height[stack[top]]) - height[bottom];
// 累加雨水量 = 宽度 × 高度
result += distance * boundedHeight;
}
// 将当前柱子索引入栈
stack[++top] = i;
}
// 释放动态分配的栈内存
free(stack);
// 返回接住的雨水总量
return result;
}
加载评论中...