42. 接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 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 * 10^4
0 <= height[i] <= 10^5

代码

完整代码

#include <stdbool.h>int trap(int* height, int heightSize) {int water = 0;bool needRoute = false;int lastLeftIndex = -1;int level = 1;for (int i = 0; i < heightSize; i++){if(height[i] >= level){if(height[i] > level){needRoute = true;}if(lastLeftIndex == -1){}else{water += (i - lastLeftIndex - 1) > 0 ? (i - lastLeftIndex - 1) : 0;if(((i - lastLeftIndex - 1) > 0 ? (i - lastLeftIndex - 1) : 0) > 0){// printf("index %d, level %d\n",i, level);// printf("water += %d \n",(i - lastLeftIndex - 1));}}// printf("index %d, level %d\n",i, level);// printf("left wall refresh %d\n",height[i]);lastLeftIndex = i;}if(i == heightSize - 1){level++;lastLeftIndex = -1;if(needRoute){needRoute = false;i = -1;}}}return water;
}

思路分析

按层遍历：从第一层（高度为 1）开始，逐层扫描，计算每一层的雨水量。
水位标记：对于每一层，遍历数组，记录当前层的左右墙壁以及水平距离，计算当前层的雨水量。
累加求和：将每一层的雨水量累加，得到总的雨水量。
时间复杂度：考虑每一层的遍历，总的时间复杂度为 O(n * h)，其中 n 是数组 height 的长度，h 是数组 height 的最大值。

拆解分析

按层遍历：从高度为 1 开始，逐层向上扫描。
水位标记：对于每一层，记录左右墙壁以及水平距离，计算当前层的雨水量。
累加求和：将每一层的雨水量累加，得到总的雨水量。

复杂度分析

时间复杂度：考虑每一层的遍历，总的时间复杂度为 O(n * h)，其中 n 是数组 height 的长度，h 是数组 height 的最大值。
空间复杂度：O(1)，只使用常数级别的额外空间。

结果

在这里插入图片描述

一题多解

双指针法

代码

#define MIN(a,b) ((a) < (b) ? (a) : (b))int trap(int* height, int heightSize) {if (heightSize <= 2) return 0; // 边界情况处理int water = 0;int left = 0, right = heightSize - 1;int lefth = 0, righth = 0;int totalsize = 0;while (left < right) {if (height[left] <= height[right]) { // 左边界小于等于右边界if (height[left] >= lefth) {lefth = height[left]; // 更新左边界的高度} else {water += lefth - height[left]; // 累加雨水量}left++; // 左边界右移} else { // 右边界小于左边界if (height[right] >= righth) {righth = height[right]; // 更新右边界的高度} else {water += righth - height[right]; // 累加雨水量}right--; // 右边界左移}}return water;
}