力扣经典题目：接雨水

问题描述

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

解题思路

由示例给出的图可知，接满水后，柱子原来的最高位置不变，柱子两侧的水面高度则由两侧从近到远的最大值来决定，并逐步降低。因此，解题思路如下：

1. 求出柱子高度最大值，以及所在位置；
2. 最左侧到柱子最高位进行遍历，求当前最大值，并将当前最大值作为当前柱子的水面高度；
3. 最右侧到柱子最高位进行遍历，求当前最大值，并将最大值作为当前柱子的水面高度；
4. 初始化雨水量为0，遍历各柱子，求水面高度与柱子高度的高差，累加到雨水量中；
5. 输出雨水量；

代码实现

以示例1和示例2为输入条件，根据解题思路编写代码。

int trap(vector<int>& height)//接雨水
{
	//搜索最大高度及位置
	int maxHeight = INT_MIN;//容器最大高度
	int index = -1;//最大高度所在位置
	for (int i = 0; i < height.size(); ++i)
	{
		if (height[i] <= maxHeight) continue;
		maxHeight = height[i];
		index = i;
	}

	//计算各个位置水面高度
	vector<int> topHeight(height.size(), 0);//接满雨水后水面高度
	int currentHeight = height[0];
	for (int i = 0; i <= index; ++i)//左侧水面高度计算
	{
		if (height[i] > currentHeight) currentHeight = height[i];
		topHeight[i] = currentHeight;
	}
	currentHeight = height.back();
	for (int i = height.size() - 1; i >= index; --i)//右侧水面高度计算
	{
		if (height[i] > currentHeight) currentHeight = height[i];
		topHeight[i] = currentHeight;
	}

	//计算总水量
	int sumRain = 0;//总水量
	for (int i = 0; i < height.size(); ++i)
	{
		sumRain = sumRain + (topHeight[i] - height[i]);//高度差*宽度
	}
	return sumRain;
}

int main()
{
	vector<int> height = { 0,1,0,2,1,0,1,3,2,1,2,1 };
	int result = trap(height);
	std::cout << result << endl;
	height = { 4,2,0,3,2,5 };
	result = trap(height);
	std::cout << result << endl;
}

运行结果

从上文可知，示例1、2对应的雨水总量为6、9；

代码运行结果见下图：

对比可知，运行结果符合预期。