algorithm - 用洞(0)收集雨水 ii(LeetCode)

Question

https://leetcode.com/problems/trapping-rain-water-ii/

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

稍微补充一下，如果上面有一个洞，整个平台都在空中？它实际可以存储多少？

虽然我可以寻找孔周围的边界区域并计算那里浪费了多少水，但我只能定义一个矩形边界区域(情况 1)，但对于第二种情况，您如何定位和计算该区域中的水:

如果我只是寻找由灰线定义的边界区域组成的矩形区域，计算这里储存的水，然后从总数中减去，绿色区域中储存的水将被移除，这不应该被移除。更大的问题是，如果它根本不存在怎么办？

或者我是否缺少任何方法，欢迎提出任何和所有建议。

Answer 1

这是对我有用的方法。

我查看的是单独的单元格，而不是区域。

设 a[i][j] 是组合石头(或任何 Material )和上面的水的总高度。

然后我们有:

a[i][j] = max(height[i][j], min(a[i+1][j], a[i][j+1], a[i-1][j], a[i][j-1]))

“max”部分是为了防止数值小于stone部分。而“最小”部分是为了确保水被相邻的细胞保留。

对于边界，水位为零，所以 a[i][j] = height[i][j]。对于其他单元格，我们可以从一个非常大的数字开始。

稍微说明一下:假设您确定相邻单元格的水位不能超过 7(例如)。那么当前单元格的水位也不能超过 7:实际上没有任何东西可以阻止水流向相邻单元格的方向。

顺便说一句，如果你在一个单元格中有一个“洞”，那么 a[i][j] = 0 因为那里不能积聚水。

我们可以重复应用该公式作为一种“放松”，直到不再可能为止。当不再可能时，我们有最终配置，我们只需要计算水量。

为了使程序高效，我们可以从上到下应用:

a[i][j] = max(height[i][j], min(a[i-1][j], a[i][j-1]))

然后从下往上应用:

a[i][j] = max(height[i][j], min(a[i+1][j], a[i][j+1]))

在至少有一个单元格值发生变化的情况下再次重复。