今日题目

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

思路

在昨天的题目中，我们讨论了什么情况下应该考虑使用图论方法来解题。

现在我们可以将这个判断标准应用到本题：本题中水可以从四个方向流动，这意味着存在后效性。

因此，我们需要采用图论方法。

每个格子能储存多少水，取决于它与其最低邻居之间的高度差（类似于心理学课上常见的木桶效应——木桶的容量由最短的那块木板决定）。

需要说明的是，水墙本身也可以作为一种墙，参与高度的计算。

要知道墙的高度，我们首先需要生成一堵墙。但墙在哪里？

最自然的想法是将图的最外层边界作为初始墙（就像示例二中用最外层边界储水的情况）。

然后我们找到墙上最低的点，向内扩展新的墙。也就是说，如果内部邻居比当前墙上的点更高，则该邻居成为新墙的一部分；否则，该内部点可以储水，水面高度与当前墙点相同，从而形成水墙。

由于我们总是选取墙上最低的点，墙的其他部分高度均不低于该点，这意味着当前墙高就是内部能储水量的上限。

方法

这里可以使用优先队列高效地找到墙上最低的点。

然后按照上述算法执行：

  1. 创建初始墙

  2. 循环：

    1. 找到墙上最低的点

    2. 生成新的实体墙或水墙

  3. 结束循环

  4. 累加所有水墙的额外高度

复杂度

  • 时间复杂度：$O(NM\times log(NM))$

  • 空间复杂度：$O(NM)$

代码

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if len(heightMap) < 3 or len(heightMap[0]) < 3:
            return 0
        
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        vis = []
        n, m = len(heightMap), len(heightMap[0])
        q = []
        for i in range(n):
            heappush(q, (heightMap[i][0], i, 0))
            heappush(q, (heightMap[i][-1], i, m - 1))
            vis.append((i, 0))
            vis.append((i, m-1))
        for i in range(1, m - 1):
            heappush(q, (heightMap[0][i], 0, i))
            heappush(q, (heightMap[-1][i], n - 1, i))
            vis.append((0, i))
            vis.append((n-1, i))
        
        vis = set(vis)
        ans = 0

        while len(q) > 0:
            h, x, y = heappop(q)
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m or (nx,ny) in vis:
                    continue
                if heightMap[nx][ny] < h:
                    ans += h - heightMap[nx][ny]
                heappush(q, (max(h, heightMap[nx][ny]), nx, ny))
                vis.add((nx, ny))
        return ans