接雨水 II
难度:
标签:
题目描述
Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.
Example 1:
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] Output: 4 Explanation: After the rain, water is trapped between the blocks. We have two small ponds 1 and 3 units trapped. The total volume of water trapped is 4.
Example 2:
Input: 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]] Output: 10
Constraints:
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104
代码结果
运行时间: 126 ms, 内存: 18.5 MB
// Java Stream 不适合用来处理这个问题，因为它需要复杂的状态管理和优先级队列的操作。
// 因此，解决这个问题的最有效方式是使用常规的循环和队列，而不是使用Java Streams。
解释
方法:
该题解使用了最小堆来解决接雨水问题。首先将矩阵周边的元素加入最小堆，并初始化水位数组water。然后不断从堆顶取出高度最小的元素，判断其四周是否有未访问过的元素，如果有就计算该位置能接的雨水量，并将其加入最小堆。重复这个过程直到堆为空，最终的接雨水总量就是答案。
时间复杂度:
O(mn * log(mn))
空间复杂度:
O(mn)
代码细节讲解
🦆
为什么在初始化时，只将矩阵的边界元素加入最小堆，而不是全部元素？
▷🦆
在计算可以接的雨水量时，为什么要比较当前元素的高度与水位数组中的水位，而不是直接使用矩阵中的高度？
▷🦆
在从最小堆中取出元素后，更新四周元素的策略为何选择只更新未访问过的元素？
▷