面试了一个字节的候选人，我怕他觉得简单，是在侮辱字节，让他写3D接雨水，结果他没写出来。

架构狂人

发布于 2024-05-10 06:02:30

23800

代码可运行

文章被收录于专栏：架构狂人架构狂人

运行总次数：0

代码可运行

我们都知道字节喜欢考算法题，并且有些时候考的比较难，这让很多想进入字节的程序员感到头疼。所以当字节的程序员到其他大厂面试的时候，大家也喜欢出一些高难度的算法题。

这不最近一字节员工在面试的时候，一网友怕他嫌题简单侮辱字节，所以就索性让他写3D接雨水，结果他没写出来。

我们知道LeetCode有两道接雨水的题，一道是二维的，一道是三维的，并且难度都是hard，其中二维的接雨水我们前面刚讲过：《二维接雨水》。

对于该字节员工没有写出3D接雨水问题，很多网友都是一片嘲讽，我们来看下大家是怎么评论的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第407题：接雨水 II。这题也是很多大厂的面试题，比如字节，京东，携程，尤其是京东特别爱考这题。

问题描述

来源：LeetCode第407题

难度：困难

很给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例1：

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 输出: 4 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例2：

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]] 输出: 10

m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 10^4

问题分析

对于3D接雨水问题，首先边上的位置是不能盛水的，只有里面的才有可能盛水。我们把边上围成的一圈看成一个桶，如下图所示：

根据木桶原理，桶中水的高度取决于最小的那块木板，所以我们可以计算和最短木板挨着的位置（上下左右四个方向）所能容纳的水量，如果该位置比最短木板还高，明显是不能盛水的，该位置只有低于木板的高度，才会盛水。

每个位置计算之后，为了方便每次查找最小值，我们可以把计算之后的位置添加到最小堆中，下一次就从堆中继续取出最小值，在计算他的上下左右四个方向。。。

如下图所示，我们看到桶的一周最矮的是 4 ，计算和它挨着的高度为 3 的位置，他可以盛一个单位的水，盛水之后他的高度就变成 4 了。然后和里面的 4 挨着的有 8 和 9 ，他们都比 4 大，所以他们是不能盛水的。

接着我们再取出最小值 8 ，和它挨着的 6 是可以盛水的，一直重复上面的步骤，直到所有点都计算完为止。

我们还可以这样来想一下，因为使用的是BFS的遍历方式，每次都是从堆中取最小值遍历他的上下左右四个方向，而堆中的元素都是遍历过的，所以所有计算过的位置都是连通的，从最外面一圈开始，逐渐往内计算，类似于农村包围城市，最终全部包围。

JAVA：

public int trapRainWater(int[][] heightMap) {
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> a[2]));
    int m = heightMap.length;// 矩阵的高
    int n = heightMap[0].length;// 矩阵的宽
    boolean[][] visited = new boolean[m][n];

    // 先把四周所有元素添加到堆中。
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                pq.offer(new int[]{i, j, heightMap[i][j]});
                visited[i][j] = true;
            }

    int water = 0;// 接的雨水量
    // 上下左右
    int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    while (!pq.isEmpty()) {
        int[] nums = pq.poll();
        for (int[] dir : dirs) {// 遍历当前出队元素的上下左右四个方向。
            int x = nums[0] + dir[1];
            int y = nums[1] + dir[0];
            // 不能越界
            if (y < 0 || y >= n || x < 0 || x >= m || visited[x][y])
                continue;
            visited[x][y] = true;// 标记为已计算过
            water += Math.max(0, nums[2] - heightMap[x][y]);// 计算水量
            pq.add(new int[]{x, y, Math.max(nums[2], heightMap[x][y])});
        }
    }
    return water;
}

C++：

public:
    int trapRainWater(vector<vector<int>> &heightMap) {
        struct TupleCompare {
            bool operator()(const tuple<int, int, int> &a, const tuple<int, int, int> &b) const {
                return get<2>(a) > get<2>(b);
            }
        };
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, TupleCompare> pq;//  最小堆
        int m = heightMap.size();// 矩阵的高
        int n = heightMap[0].size();// 矩阵的宽
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        // 先把四周所有元素添加到堆中。
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    pq.emplace(i, j, heightMap[i][j]);
                    visited[i][j] = true;
                }

        int water = 0;// 接的雨水量
        // 上下左右
        int dirs[][2] = {{0,  -1},
                         {0,  1},
                         {-1, 0},
                         {1,  0}};
        while (!pq.empty()) {
            tuple nums = pq.top();
            pq.pop();
            for (const auto &dir: dirs) {// 遍历当前出队元素的上下左右四个方向。
                int x = get<1>(nums) + dir[0];
                int y = get<0>(nums) + dir[1];
                // 不能越界
                if (x < 0 || x >= n || y < 0 || y >= m || visited[y][x])
                    continue;
                visited[y][x] = true;// 标记为已计算过
                water += max(0, get<2>(nums) - heightMap[y][x]);// 计算水量
                pq.emplace(y, x, max(get<2>(nums), heightMap[y][x]));
            }
        }
        return water;
    }

Python：

def trapRainWater(self, heightMap: List[List[int]]) -> int:
    pq = []
    m = len(heightMap)  # 矩阵的高
    n = len(heightMap[0])  # 矩阵的宽
    visited = [[False for _ in range(n)] for _ in range(m)]

    # 先把四周所有元素添加到堆中。
    for i in range(m):
        for j in range(n):
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                heapq.heappush(pq, (heightMap[i][j], i, j))
                visited[i][j] = True

    water = 0  # 接的雨水量
    # 上下左右
    dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]]
    while pq:
        n0, n1, n2 = heapq.heappop(pq)
        for dx, dy in dirs:  # 遍历当前出队元素的上下左右四个方向。
            x = n1 + dx
            y = n2 + dy
            # 不能越界
            if x < 0 or x >= m or y < 0 or y >= n or visited[x][y]:
                continue
            visited[x][y] = True  # 标记为已计算过
            water += max(0, n0 - heightMap[x][y])  # 计算水量
            heapq.heappush(pq, (max(n0, heightMap[x][y]), x, y))
    return water