Python PriorityQueue Solution
\'\'\'\nclass Solution:\n\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        from queue import PriorityQueue\n        if not heightMap or
\'\'\'\nclass Solution:\n\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        from queue import PriorityQueue\n        if not heightMap or heightMap == []:\n            return 0\n        \n        m,n = len(heightMap), len(heightMap[0])\n        q = PriorityQueue()\n        last = -float(\'inf\')\n        res = 0\n        # add all surrounding points of the matrix\n        for i in range(m):\n            for j in range(n):\n                if i == 0 or i == m -1 or j == 0 or j == n-1:\n                    q.put((heightMap[i][j], i, j))\n                    heightMap[i][j] = None\n                    \n        while not q.empty():\n            point = q.get()\n\t\t\t# keep track of the largest height value poped from queue\n            last = max(last, point[0])\n            \n\t\t\t# check the neighbors of 4 directions of the poped point\n            for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:\n                x = dx + point[1]\n                y = dy + point[2]\n                if x >= 0 and x < m and y >= 0 and y < n and heightMap[x][y] != None:\n                    if heightMap[x][y] < last:\n\t\t\t\t\t\t# if the new height value is smaller than "last", add the difference as final result\n                        res += last - heightMap[x][y]\n                    q.put((heightMap[x][y], x, y))\n                    heightMap[x][y] = None\n        return res\n\'\'\'\nThis solution is based on PriorityQueue. Firstly, I add all the surrounding point of the matrix into the queue. Then I use a while loop to pop the points one by one. One a point is poped, I will search for its surrounding 4 points to see if they had been already searched (None) or they can be added to the queue. "last" is the variable to track the largest height value poped from the queue and every time a new height about to add to queue with smaller value than "last", the difference of "last" and the new height will be added to "res" variable as a part of final response.\n\nTime Complexity is O(MN log(MN)), Space Complexity is O(MN)\n
['Heap (Priority Queue)']