How can I optimize Trapping Rain Water II if the matrix size is very large?

For large matrices, ensure you use the priority queue efficiently to minimize unnecessary operations. Avoid naive flood-fill algorithms that don't utilize a heap for optimal processing.

Can I use a brute force solution to solve Trapping Rain Water II?

While brute force is possible, it is inefficient for large matrices. The BFS with priority queue approach offers a much faster solution with a better time complexity.

What is the main advantage of using BFS with a priority queue for this problem?

The main advantage is that it allows us to simulate the flow of water from the boundary inward, ensuring an optimal solution with minimal processing time, using logarithmic heap operations.

What is the time complexity of the optimal solution for Trapping Rain Water II?

The time complexity is O(m * n * log(m * n)), where m and n are the dimensions of the matrix. This is due to the priority queue operations, which take logarithmic time for each cell.

How do I handle edge cases in Trapping Rain Water II?

Edge cases include very small matrices or matrices where all cells have the same elevation. The algorithm handles these efficiently, but make sure to verify that your implementation works for these edge cases.

#407

Hard

auto_awesome图·搜索

LeetCode 题解工作台

接雨水 II

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。示例 1: 输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 输出: 4 解释: 下雨后，雨水将会被上图蓝色…

数组广度优先搜索堆（优先队列）矩阵

题目描述

给你一个 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⁴

lightbulb

解题思路

方法一：优先队列（小根堆）

接雨水问题的变种，由于矩阵的边界上的高度是确定的，因此可以将矩阵的边界上的高度加入优先队列，然后从优先队列中取出最小的高度，然后将其四周的高度与其比较，如果四周的高度小于当前高度，则可以接雨水，接雨水的体积为当前高度减去四周的高度，然后将较大的高度加入优先队列，重复上述过程，直到优先队列为空。

时间复杂度 $O(m \times n \times \log (m \times n))$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        vis = [[False] * n for _ in range(m)]
        pq = []
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heappush(pq, (heightMap[i][j], i, j))
                    vis[i][j] = True
        ans = 0
        dirs = (-1, 0, 1, 0, -1)
        while pq:
            h, i, j = heappop(pq)
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if x >= 0 and x < m and y >= 0 and y < n and not vis[x][y]:
                    ans += max(0, h - heightMap[x][y])
                    vis[x][y] = True
                    heappush(pq, (max(h, heightMap[x][y]), x, y))
        return ans

speed

复杂度分析

指标	值
时间	O(m \cdot n \times \log{m \cdot n})
空间	O(m \times n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of how BFS and priority queues can be applied to 2D matrix problems.
question_mark
The candidate identifies key edge cases and efficiently handles varying matrix sizes and elevations.
question_mark
The candidate can explain the flow of water across different heights in a matrix and why boundary processing is crucial.

warning

常见陷阱

外企场景

error
Failing to use a priority queue effectively may lead to inefficient traversal and incorrect water trapping calculations.
error
Overcomplicating the problem with unnecessary space or time-consuming operations.
error
Not handling edge cases where the matrix is very small or where the matrix has constant elevation values, which could lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the solution without a priority queue, relying on a simpler flood-fill approach.
arrow_right_alt
Optimizing space complexity by using in-place modifications to the heightMap matrix.
arrow_right_alt
Handling varying matrix shapes (non-square matrices) and ensuring correctness in all cases.

help

常见问题

外企场景

继续练习

#675 为高尔夫比赛砍树 #778 水位上升的泳池中游泳 #1263 推箱子