【前缀和】42. 接雨水

本文涉及知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

LeetCode42. 接雨水

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

提示：
n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

枚举

vWater[i] 记录第i个柱子水的高度。
令 leftMax =max(height[0…i-1])
rightMax = max(height[i+1…])
如果水高于 leftMax 或 rightMax，水会流走。故水的高度为：min(leftMax,rightMax) - height[i]
结果为负，则为0。
更改leftMax为max(height[0…i])，rightMax类似。则不需要考虑负数。
时间复杂度：O(n)

代码

核心代码

class Solution {
public:
	int trap(vector<int>& height) {
		const int n = height.size();
		vector<int> vLeft = height;
		for (int i = 1; i < n; i++) {
			vLeft[i] = max(vLeft[i], vLeft[i - 1]);
		}
		int iRightMax = 0;
		int iRet = 0;
		for (int i = n - 1; i >= 0; i--) {
			iRightMax = max(iRightMax, height[i]);
			const int iWater = min(iRightMax, vLeft[i]);
			iRet += iWater - height[i];
		}
		return iRet;
	}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	vector<int> height;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{	
			height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
			auto res = Solution().trap(height);
			AssertEx(6,res);
		}
		TEST_METHOD(TestMethod1)
		{
			height = { 4, 2, 0, 3, 2, 5 };
			auto res = Solution().trap(height);
			AssertEx(9, res);
		}
		
	};
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛