專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

隨著2025年春節的日益臨近，各大互聯網公司的春節假期安排和年終獎發放成為了廣大員工和網友們熱議的話題。

12月23日，京東發布了2024年年終獎發放計劃，這是京東要實現從16薪邁向20薪的第一年。實現17薪的部門內年度績效A+的員工將實現20薪，采銷崗平均23薪，差不多相當于干一年發兩年的工資，這年終獎確實挺誘人。

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

來看下今天的算法題，這題是LeetCode的第695題：島嶼的最大面積。

問題描述

來源：LeetCode第695題

難度：中等

給你一個大小為 m x n 的二進制矩陣 grid 。島嶼是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在水平或者豎直的四個方向上相鄰。你可以假設 grid 的四個邊緣都被 0（代表水）包圍著。

島嶼的面積是島上值為 1 的單元格的數目。計算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。

示例1：

輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 輸出：6 解釋：答案不應該是 11 ，因為島嶼只能包含水平或垂直這四個方向上的 1 。

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 50

• grid[i][j] 為 0 或 1

問題分析

這題讓計算島嶼的最大面積，島嶼的面積是通過上下左右相連接的 1 的個數。這題有多種解決方式，BFS，DFS和并查集都可以解決，之前我們講過這道題，當時使用的是 BFS- ，這里我們使用 DFS 再來解這道題。

關于DFS的知識我們在 中也講過，不過這里遍歷的不是圖，而是矩陣，實際上原理都是一樣的。

在矩陣中每個位置最多只有上下左右四個和它相連，我們 遍歷矩陣的每一個位置，如果當前位置是 1 ，表示它是島嶼，然后開始計算島嶼的面積。 就是以當前位置為起始點沿著它的上下左右四個方向查找，如果遇到 1 ，說明它們是同一個島嶼，累加面積，然后再把它變成 0 ，表示該位置已經計算過了，防止重復計算，最后只需要返回最大面積即可。

這里還要注意遍歷的時候不能越界，只能訪問矩陣內的位置。

JAVA：

public int maxAreaOfIsland(int[][] grid) {     int m = grid.length, n = grid[0].length;// 矩陣的寬和高     int ans = 0;// 記錄最大面積     for (int i = 0; i < m; i++)         for (int j = 0; j < n; j++)             if (grid[i][j] == 1) // 當前位置如果是 1 ，開始計算                 ans = Math.max(ans, dfs(grid, i, j, m, n));     return ans; } public int dfs(int[][] grid, int i, int j, int m, int n) {     // 邊界條件的判斷，不能越界     if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {         // 當前位置如果是1，為了防止重復計算就把他置為0，然后再從他的上下左右四個方向開始查找         grid[i][j] = 0;         return 1 + dfs(grid, i + 1, j, m, n) + dfs(grid, i - 1, j, m, n)                 + dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n);     }     return 0; }

C++：

public:     int maxAreaOfIsland(vector

 > &grid) {         int m = grid.size(), n = grid[0].size();// 矩陣的寬和高         int ans = 0;// 記錄最大面積         for (int i = 0; i < m; i++)             for (int j = 0; j < n; j++)                 if (grid[i][j] == 1) // 當前位置如果是 1 ，開始計算                     ans = max(ans, dfs(grid, i, j, m, n));         return ans;     }     int dfs(vector

 > &grid, int i, int j, int m, int n) {         // 邊界條件的判斷，不能越界         if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {             // 當前位置如果是1，為了防止重復計算就把他置為0，然后再從他的上下左右四個方向開始查找             grid[i][j] = 0;             return 1 + dfs(grid, i + 1, j, m, n) + dfs(grid, i - 1, j, m, n)                    + dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n);         }         return 0;     }

Python：

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:     def dfs(i, j):         # 邊界條件的判斷，不能越界         if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:             # 當前位置如果是1，為了防止重復計算就把他置為0，然后再從他的上下左右四個方向開始查找             grid[i][j] = 0             return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j - 1) + dfs(i, j + 1)         return 0     m, n = len(grid), len(grid[0])  # 矩陣的寬和高     ans = 0  # 記錄最大面積     for i in range(m):         for j in range(n):             if grid[i][j] == 1:  # 當前位置如果是 1 ，開始計算                 ans = max(ans, dfs(i, j))     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。