[LeetCode]Trapping Rain Water II

不是很有思路的题目。之前的想法是模拟从最外一圈格子开始倒水，直到水没有办法留存下来，但是这样做的话时间复杂度太高。DP的思路的话，一个格子的存水量是取决于四周的格子，所以肯定是应该从外向内DP，但是具体遵循什么样的DP 公式却不好推导出来。看了别人的解答，才发现确实是很不错的解法。我们的思路是从外向内DP，那么存水量是取决于最短的那一块板子。我们从最外层的格子的集合s开始，我们每一次取最短的格子b出来，然后算它四周格子x的存水量，因为x的存水量就由b决定了。因为我们有一个不变的事实是，所有在s上和之前在s上的格子一直都会围城一个圈，而这个圈的存水高度就由当前的b（组成圈的格子不一样的情况下，b的高度很显然也不一样）决定，画个图会很好理解。之后更新x格子存水的高度，然后将x插入s，假设x高度小于b大么它的高度应该更新为b，因为剩下格子的存水高度不会小于b了，如果大于b，那么x高度不变。一直循环直到s为空，最后算出总存水量，时间复杂度O(n * log n)，n是格子总数，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int trapRainWater(vector<vector<int>>& heightMap) {
	int m = heightMap.size(), n = m? heightMap[0].size(): 0;
	auto comp = [&](const int i, const int j){ return heightMap[i / n][i % n] > heightMap[j / n][j % n]; };
	priority_queue<int, vector<int>, decltype(comp)> pq(comp);
	vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	vector<bool> visited(m * n, false);
	for(int i = 0; i < m; ++i)
	{
	pq.push(i * n);
	pq.push(i * n + n - 1);
	visited[i * n] = visited[i * n + n - 1] = true;
	}
	for(int i = 0; i < n; ++i)
	{
	pq.push(i);
	pq.push((m - 1) * n + i);
	visited[i] = visited[(m - 1) * n + i] = true;
	}
	int vol = 0;
	while(pq.size())
	{
	int curr = pq.top(), i = curr / n, j = curr % n;
	pq.pop();
	for(auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if(x >= 0 && x < m && y >= 0 && y < n && !visited[x * n + y])
	{
	visited[x * n + y] = true;
	vol += heightMap[i][j] > heightMap[x][y]? heightMap[i][j] - heightMap[x][y]: 0;
	heightMap[x][y] = max(heightMap[i][j], heightMap[x][y]);
	pq.push(x * n + y);
	}
	}
	}
	return vol;
	}
	};

view raw Trapping Rain Water II.cpp hosted with ❤ by GitHub