專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友說訂婚的前兩個月老公（結(jié)婚之前應(yīng)該叫相親對象）被裁了，結(jié)果繼續(xù)籌備婚禮，婚也結(jié)了，最后還是沒有找到工作，已經(jīng)失業(yè)四個月了，現(xiàn)在也不敢要孩子。

我覺得如果是程序員，失業(yè)4個月還找不到工作，可以考慮先找一份工作過渡一下，實(shí)在不行就轉(zhuǎn)行吧。34歲確實(shí)挺尷尬的一個年齡，雖然現(xiàn)在各互聯(lián)網(wǎng)大廠一直在招人，并且給的工資也不低，但他們主要招的是應(yīng)屆畢業(yè)生。

至于網(wǎng)友說的換個對象，當(dāng)做玩笑看看就行了，不要當(dāng)真。人無千日好，花無百日紅，每個人都會經(jīng)歷過事業(yè)的低谷，只要別一直在低谷躺著就行。

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

來看下今天的算法題，這題是LeetCode的第407題：接雨水 II

問題描述

來源：LeetCode第407題

難度：困難

很給你一個 m x n 的矩陣，其中的值均為非負(fù)整數(shù)，代表二維高度圖每個單元的高度，請計(jì)算圖中形狀最多能接多少體積的雨水。

示例1：

輸入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 輸出: 4 解釋: 下雨后，雨水將會被上圖藍(lán)色的方塊中。總的接雨水量為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接雨水問題，首先邊上的位置是不能盛水的，只有里面的才有可能盛水。我們把邊上圍成的一圈看成一個桶，如下圖所示：

根據(jù)木桶原理， 桶中水的高度取決于最小的那塊木板 ，所以我們可以計(jì)算和最短木板挨著的位置（上下左右四個方向）所能容納的水量，如果該位置比最短木板還高，明顯是不能盛水的，該位置只有低于木板的高度，才會盛水。

每個位置計(jì)算之后，為了方便每次查找最小值，我們可以把計(jì)算之后的位置添加到最小堆中，下一次就從堆中繼續(xù)取出最小值，在計(jì)算它的上下左右四個方向。。。

如下圖所示，我們看到桶的一周最矮的是 4 ，計(jì)算和它挨著的高度為 3 的位置，他可以盛一個單位的水，盛水之后他的高度就變成 4 了。然后和里面的 4 挨著的有 8 和 9 ，他們都比 4 大，所以他們是不能盛水的。

接著我們再取出最小值 8 ，和它挨著的 6 是可以盛水的，一直重復(fù)上面的步驟，直到所有點(diǎn)都計(jì)算完為止。

我們還可以這樣來想一下，因?yàn)槭褂玫氖荁FS的遍歷方式，每次都是從堆中取最小值遍歷它的上下左右四個方向，而堆中的元素都是遍歷過的，所以所有計(jì)算過的位置都是連通的，從最外面一圈開始，逐漸往內(nèi)計(jì)算，類似于農(nóng)村包圍城市，最終全部包圍。

JAVA：

public int trapRainWater(int[][] heightMap) {     PriorityQueue

  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) {// 遍歷當(dāng)前出隊(duì)元素的上下左右四個方向。             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;// 標(biāo)記為已計(jì)算過             water += Math.max(0, nums[2] - heightMap[x][y]);// 計(jì)算水量             pq.add(new int[]{x, y, Math.max(nums[2], heightMap[x][y])});         }     }     return water; }

C++：

public:     int trapRainWater(vector

 > &heightMap) {         struct TupleCompare {             bool operator()(const tuple

  &a, const tuple

  &b) const {                 return get<2>(a) > get<2>(b);             }         };         priority_queue int,  int,  int>,  vector int,  int,  int>>, TupleCompare> pq; //  最小堆          int m = heightMap.size(); // 矩陣的高          int n = heightMap[ 0].size(); // 矩陣的寬          vector

 > visited(m, vector

 (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) { // 遍歷當(dāng)前出隊(duì)元素的上下左右四個方向。                  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; // 標(biāo)記為已計(jì)算過                 water += max( 0, get< 2>(nums) - heightMap[y][x]); // 計(jì)算水量                 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:  # 遍歷當(dāng)前出隊(duì)元素的上下左右四個方向。             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  # 標(biāo)記為已計(jì)算過             water += max(0, n0 - heightMap[x][y])  # 計(jì)算水量             heapq.heappush(pq, (max(n0, heightMap[x][y]), x, y))     return water

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計(jì)做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。