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

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

在近在網(wǎng)上看到一個視頻，一HR在幫內(nèi)地一家非常大的手機(jī)品牌在香港招聘的時候，要求年齡限制在35歲以下，引起該HR的痛批。至于是哪家手機(jī)品牌，視頻中沒有透露，我們也不要隨便猜測。只是這個行為在內(nèi)地已經(jīng)司空見慣了，雖然批評的聲音一直存在，但大家好像都已經(jīng)習(xí)慣了。至于在香港應(yīng)該還沒有這方面的先例，有網(wǎng)友評論道：“過分了。內(nèi)地大企業(yè)想把劣質(zhì)招聘文化帶到香港！必須拒絕！

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

來看下今天的算法題，這題是LeetCode的第417題：太平洋大西洋水流問題。

問題描述

來源：LeetCode第417題

難度：中等

有一個 m × n 的矩形島嶼，與 太平洋 和 大西洋 相鄰。“太平洋” 處于大陸的左邊界和上邊界，而 “大西洋” 處于大陸的右邊界和下邊界。

這個島被分割成一個由若干方形單元格組成的網(wǎng)格。給定一個 m x n 的整數(shù)矩陣 heights ， heights[r][c] 表示坐標(biāo) (r, c) 上單元格 高于海平面的高度 。

島上雨水較多，如果相鄰單元格的高度小于或等于當(dāng)前單元格的高度，雨水可以直接向北、南、東、西流向相鄰單元格。水可以從海洋附近的任何單元格流入海洋。

返回網(wǎng)格坐標(biāo) result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水從單元格 (ri, ci) 流動既可流向太平洋也可流向大西洋。

示例1：

輸入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 輸出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例2：

輸入: heights = [[2,1],[1,2]] 輸出: [[0,0],[0,1],[1,0],[1,1]]

• m == heights.length

• n == heights[r].length

• 1 <= m, n <= 200

• 0 <= heights[r][c] <= 10^5

問題分析

這題很繞，總結(jié)起來實(shí)際上就一句話： 哪些位置的水既能流到太平洋又能流到大西洋 。

直接計(jì)算比較麻煩，我們 先計(jì)算哪些位置的水可以流到太平洋，在計(jì)算哪些位置的水可以流到大西洋 ，最后在枚舉所有的位置，判斷哪些位置的水既能流到太平洋又能流到大西洋。

我們知道太平洋沿岸的水肯定是能流到太平洋的，水往低處流，這里我們 逆向思維 ，讓水往高處流。從太平洋沿岸的位置開始遍歷，如果下一個位置比當(dāng)前位置高，說明下一個位置一定可以通過當(dāng)前位置流到太平洋的，如下圖所示。同理大西洋也一樣。

JAVA：

public List
         
 > pacificAtlantic( int[][] heights) {     List > ans =  new ArrayList<>();      int n = heights.length, m = heights[ 0].length;      // 哪些位置可以到達(dá)太平洋      boolean[][] pacific =  new  boolean[n][m]; // 太平洋      // 哪些位置可以到達(dá)大西洋      boolean[][] atlantic =  new  boolean[n][m]; // 大西洋     Queue< int[]> pQueue =  new LinkedList<>();     Queue< int[]> aQueue =  new LinkedList<>();      // 四周邊界      for ( int i =  0; i < n; i++) {         pQueue.offer( new  int[]{i,  0});         aQueue.offer( new  int[]{i, m -  1});         pacific[i][ 0] =  true;         atlantic[i][m -  1] =  true;     }      for ( int i =  0; i < m; i++) {         pQueue.offer( new  int[]{ 0, i});         aQueue.offer( new  int[]{n -  1, i});         pacific[ 0][i] =  true;         atlantic[n -  1][i] =  true;     }     bfs(heights, m, n, pQueue, pacific); // 先查找能夠到達(dá)太平洋的坐標(biāo)     bfs(heights, m, n, aQueue, atlantic); // 在查找能夠達(dá)到大西洋的坐標(biāo)      for ( int i =  0; i < n; i++) {          for ( int j =  0; j < m; j++) {              // 哪些位置既可以到達(dá)太平洋也可以達(dá)到大西洋              if (pacific[i][j] && atlantic[i][j])                 ans.add(Arrays.asList(i, j));         }     }      return ans; } int[][] dir =  new  int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; private void bfs(int[][] heights, int m, int n, Queue

  queue, boolean[][] visited) {      while (!queue.isEmpty()) {          int[] cur = queue.poll();          for ( int[] d : dir) {              int x = cur[ 0] + d[ 0];              int y = cur[ 1] + d[ 1];              // 水如果從位置heights[x][y]流到位置[cur[0]][cur[1]]，那么              // heights[x][y]的高度必須要大于[cur[0]][cur[1]]。              if (x <  0 || x >= n || y <  0 || y >= m || visited[x][y]                     || heights[x][y] < heights[cur[ 0]][cur[ 1]])                  continue;             visited[x][y] =  true; // 標(biāo)記可以到達(dá)             queue.offer( new  int[]{x, y});         }     } }

C++：

public:     vector

 > pacificAtlantic(vector

 > &heights) {         vector

 > ans;         int n = heights.size(), m = heights[0].size();         // 哪些位置可以到達(dá)太平洋         vector

 > pacific(n, vector

 (m, false));         // 哪些位置可以到達(dá)大西洋         vector

 > atlantic(n, vector

 (m, false));         queue int,  int>> pQueue;          queue int,  int>> aQueue;          // 四周邊界          for ( int i =  0; i < n; i++) {             pQueue.emplace(i,  0);             aQueue.emplace(i, m -  1);             pacific[i][ 0] =  true;             atlantic[i][m -  1] =  true;         }          for ( int i =  0; i < m; i++) {             pQueue.emplace( 0, i);             aQueue.emplace(n -  1, i);             pacific[ 0][i] =  true;             atlantic[n -  1][i] =  true;         }         bfs(heights, m, n, pQueue, pacific); // 先查找能夠到達(dá)太平洋的坐標(biāo)         bfs(heights, m, n, aQueue, atlantic); // 在查找能夠達(dá)到大西洋的坐標(biāo)          for ( int i =  0; i < n; i++) {              for ( int j =  0; j < m; j++) {                  // 哪些位置既可以到達(dá)太平洋也可以達(dá)到大西洋                  if (pacific[i][j] && atlantic[i][j])                     ans.push_back({i, j});             }         }          return ans;     }      int dir[ 4][ 2] = {{1,  0},                      {-1, 0},                      {0,  1},                      {0,  -1}};      void bfs(vector

 > &heights, int m, int n, queue int , int>> &q, vector

 > &visited) {          while (!q.empty()) {             pair< int,  int> cur = q.front();             q.pop();              for ( const  auto d: dir) {                  int x = cur.first + d[ 0];                  int y = cur.second + d[ 1];                  // 水如果從位置heights[x][y]流到位置[cur[0]][cur[1]]，那么                  // heights[x][y]的高度必須要大于[cur[0]][cur[1]]。                  if (x <  0 || x >= n || y <  0 || y >= m || visited[x][y]                     || heights[x][y] < heights[cur.first][cur.second])                      continue;                 visited[x][y] =  true; // 標(biāo)記可以到達(dá)                 q.emplace(x, y);             }         }     }

Python：

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:     def bfs(q, visited):         while q:             cur = q.pop()             for d in dirs:                 x = cur[0] + d[0]                 y = cur[1] + d[1]                 # 水如果從位置heights[x][y]流到位置[cur[0]][cur[1]]，那么heights[x][y] 的高度必須要大于[cur[0]][cur[1]]。                 if x < 0 or x >= n or y < 0 or y >= m or visited[x][y] or heights[x][y] < heights[cur[0]][cur[1]]:                     continue                 visited[x][y] = True  # 標(biāo)記可以到達(dá)                 q.append([x, y])     dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]     ans = []     n, m = len(heights), len(heights[0])     # 哪些位置可以到達(dá)太平洋     pacific = [[False for _ in range(m)] for _ in range(n)]     # 哪些位置可以到達(dá)大西洋     atlantic = [[False for _ in range(m)] for _ in range(n)]     pQueue = []     aQueue = []     # 四周邊界     for i in range(n):         pQueue.append([i, 0])         aQueue.append([i, m - 1])         pacific[i][0] = True         atlantic[i][m - 1] = True     for i in range(m):         pQueue.append([0, i])         aQueue.append([n - 1, i])         pacific[0][i] = True         atlantic[n - 1][i] = True     bfs(pQueue, pacific)  # 先查找能夠到達(dá)太平洋的坐標(biāo)     bfs(aQueue, atlantic)  # 在查找能夠達(dá)到大西洋的坐標(biāo)     for i in range(n):         for j in range(m):             # 哪些位置既可以到達(dá)太平洋也可以達(dá)到大西洋             if pacific[i][j] and atlantic[i][j]:                 ans.append([i, j])     return ans

筆者簡介

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