​LeetCode刷题实战407：接雨水 II

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 接雨水 II，我们先来看题面：

https://leetcode-cn.com/problems/trapping-rain-water-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.

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

此题用BFS来做。创建一个优先级队列，该队列中是将高度小的放在队首。先将四周一圈的格子加入队列中，并将这些格子的状态设为已访问过。下面开始BFS，从队列的头部取出元素，并用其高度更新海平面level，然后从该格子向四周寻找格子，如果某格子未被访问过，那么将其状态设为已访问过，然后判断如果其高度小于海平面，那么把它们的高度差加到ans中，否则不操作。接下来将该格子加入到优先级队列中。如此进行，当优先级队列为空时退出循环，返回ans。