目錄
- 零、題目描述
- 一、為什么這道題值得一看？
- 二、題目拆解：提取核心要素與約束
- 三、算法實現：基于 DFS 的面積計算
- 代碼拆解
- 時間復雜度
- 空間復雜度
- 四、與「島嶼數量」的代碼對比（一目了然看差異）
- 五、坑點總結
- 六、舉一反三
- 七、總結
零、題目描述
題目鏈接：島嶼的最大面積
示例 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 。
示例 2：
輸入：grid = [[0,0,0,0,0,0,0,0]]
輸出：0
一、為什么這道題值得一看？
如果你是第一次閱讀我的題解文章，可能會好奇‘島嶼數量’與這道題的關聯 —— 其實，「島嶼的最大面積」是「島嶼數量（LeetCode 200）」的經典進階題，兩者共享幾乎相同的搜索框架，只是在目標上從‘統計島嶼個數’變成了‘計算最大面積’。
如果你想更系統地理解「洪水灌溉算法」的基礎邏輯（比如 DFS 如何標記連通區域、如何處理邊界條件），建議先看看昨天的文章（因為算法原理類似這篇文章講解算法原理沒有上一篇細致嘿嘿）力扣 200.島嶼數量。那里詳細拆解了‘如何從 0 到 1 設計島嶼計數的代碼’，讀懂它再看今天的內容，會對‘搜索算法的復用與調整’有更清晰的認知～
如果你昨天跟著學了「島嶼數量」（LeetCode 200），那么這道題會是絕佳的“進階練習”——它和前者共享 90% 的核心邏輯，但在細節上的差異能幫你更深刻理解「搜索算法的靈活性」。
從本質上看，兩道題都是「連通區域問題」的變種：
- 前者是計數問題（統計連通區域的數量）；
- 后者是計量問題（統計單個連通區域的最大規模）。
學會這道題，你能掌握：
- 如何在搜索過程中累加數據（面積計算的核心）；
- 如何在多個結果中跟蹤最大值；
- 進一步鞏固「洪水灌溉（Flood Fill）」算法的通用框架。
二、題目拆解：提取核心要素與約束
先看原題：
給你一個由
1（陸地）和0（水）組成的二進制矩陣grid，請你計算網格中島嶼的最大面積。島嶼是由一些相鄰的1構成的組合，這里的「相鄰」要求兩個1必須在水平或者豎直的四個方向上相鄰。你可以假設grid的四個邊緣都被0包圍著。島嶼的面積是島上值為1的單元格的數目。
再結合所給的代碼框架和提示：
class Solution {
public:int maxAreaOfIsland(vector<vector<int>>& grid) {}
};
核心要素提煉:
- 題中給出的是由
vector組成的二維數組grid，元素類型是int，取值只有0（水）和1（陸地）； - 二維數組的長寬范圍是
1 ≤ m, n ≤ 50（m為行數，n為列數）； - 核心任務是：找到所有由相鄰
1組成的島嶼，計算每個島嶼的面積（1的數量），并返回其中的最大值；若沒有島嶼，返回0。
關鍵點:
- 遍歷網格：需用雙重循環遍歷每個單元格
(i,j)，檢查是否為未訪問的陸地（grid[i][j] == 1）。 - 連通性判斷：只有水平（左右）或垂直（上下）相鄰的
1屬于同一島嶼，斜對角不算，因此搜索時僅需遍歷四個方向。 - DFS/BFS 搜索：發現陸地時，需通過深度優先或廣度優先遍歷，找到該島嶼所有相連的
1，并計算面積。 - 標記已訪問：為避免重復計算，需將已統計過的
1標記為0（原地修改，無需額外空間）。 - 面積計算與最大值跟蹤：
- 對每個島嶼，通過遞歸或迭代累加
1的數量（面積）； - 用一個變量記錄所有島嶼面積中的最大值，遍歷完所有島嶼后返回該值。
- 對每個島嶼，通過遞歸或迭代累加
- 邊界處理：搜索相鄰單元格時，需檢查坐標是否在網格范圍內（
0 ≤ x < 行數且0 ≤ y < 列數），防止越界。
與「島嶼數量」的共性（可直接復用的邏輯）：
- 遍歷網格：逐個檢查每個單元格，發現未訪問的陸地（
1）時觸發搜索； - DFS 搜索：通過遞歸遍歷當前陸地的上下左右，“淹沒”（標記為
0）已訪問的陸地，避免重復計算； - 方向數組：用
dx和dy定義四個方向，簡化代碼（和昨天的dx = [1,-1,0,0], dy = [0,0,1,-1]完全相同）。
關鍵差異（今天要重點掌握的新邏輯）：
-
從“計數”到“累加面積”：
- 昨天每觸發一次 DFS，就給島嶼數量
+1； - 今天每觸發一次 DFS，需要統計這個島嶼包含多少個
1（即面積），用變量n實時累加。
- 昨天每觸發一次 DFS，就給島嶼數量
-
跟蹤最大面積：
- 每次 DFS 結束后（一個島嶼被完全“淹沒”），將當前島嶼的面積
n與全局最大面積max_size比較，更新最大值。
- 每次 DFS 結束后（一個島嶼被完全“淹沒”），將當前島嶼的面積
三、算法實現：基于 DFS 的面積計算
代碼拆解
直接結合代碼拆解核心邏輯（代碼結構和昨天高度相似，重點看注釋中標注的差異點）：
class Solution {
public:int rows, cols;int max_size = 0; // 記錄全局最大面積（差異點1）int n = 0; // 記錄當前島嶼的面積（差異點2）int dx[4] = {1, -1, 0, 0}; // 方向數組（復用）int dy[4] = {0, 0, 1, -1};int maxAreaOfIsland(vector<vector<int>>& grid) {rows = grid.size();cols = grid[0].size();for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 1) { // 發現新島嶼n = 0; // 重置當前島嶼面積（差異點3）dfs(i, j, grid); // 遍歷整個島嶼，計算面積max_size = max(max_size, n); // 更新最大面積（差異點4）}}}return max_size;}void dfs(int x, int y, vector<vector<int>>& grid) {grid[x][y] = 0; // 淹沒當前陸地（標記已訪問，復用）n++; // 當前島嶼面積+1（差異點5）// 遍歷四個方向（復用）for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];// 檢查邊界+是否為未訪問的陸地（復用）if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && grid[nx][ny] == 1) {dfs(nx, ny, grid); // 遞歸計算相鄰陸地}}}
};
核心差異點深度解析:
上面的代碼中，標為“差異點”的部分是今天的核心，我們逐個拆解：
-
變量
n和max_size的作用：n：臨時記錄當前正在遍歷的島嶼的面積，每次發現新島嶼時重置為 0；max_size：全局變量，始終存儲所有島嶼中最大的面積，每次一個島嶼遍歷結束后更新。
舉例：如果網格中有 3 個島嶼，面積分別是 3、6、2，那么
max_size會在遍歷完第一個島嶼后變為 3，第二個后變為 6，第三個后保持 6。 -
n的累加時機：
進入dfs后，先將當前陸地標記為0（避免重復訪問），然后立即執行n++——因為當前單元格是陸地（1），本身就貢獻 1 個面積。反例：如果在遞歸結束后才
n++，會漏掉當前單元格的面積，導致結果偏小。 -
max_size的更新時機：
當一個島嶼的 DFS 完全結束后（即dfs(i,j,grid)執行完畢），n已經記錄了這個島嶼的完整面積，此時用max(max_size, n)比較并更新最大值。
分步運行示例（以示例 1 中最大島嶼為例）
為了更直觀理解 n 和 max_size 的變化，我們以示例 1 中面積為 6 的島嶼為例，跟蹤代碼的關鍵執行步驟：
-
初始狀態：
遍歷網格時，首次遇到該島嶼的第一個陸地（坐標(7,7)，假設網格行索引從0開始），此時grid[7][7] == 1。 -
觸發DFS前：
- 初始化
n = 0（準備統計當前島嶼面積）； - 調用
dfs(7,7,grid)。
- 初始化
-
DFS遞歸過程：
-
第一層遞歸（7,7）：
grid[7][7]改為0（標記已訪問），n累加為1；
檢查四個方向，發現右側(7,8)和上方(6,7)是陸地，優先遞歸(7,8)。 -
第二層遞歸（7,8）：
grid[7][8]改為0，n累加為2；
檢查方向，發現上方(6,8)是陸地，遞歸(6,8)。 -
第三層遞歸（6,8）：
grid[6][8]改為0，n累加為3；
檢查方向，發現左側(6,7)是陸地，遞歸(6,7)。 -
第四層遞歸（6,7）：
grid[6][7]改為0，n累加為4；
檢查方向，發現左側(6,6)是水，下方(7,7)已訪問，繼續遞歸其他方向… -
后續遞歸：依次訪問
(6,9)、(7,9)等相連陸地，n逐步累加至6。
-
-
DFS結束后：
該島嶼的所有陸地已被“淹沒”（改為0），n的值為6；
此時比較n與max_size（初始為0），更新max_size = 6。
通過這個過程可見：n 會隨著遞歸深入實時累加，而 max_size 僅在整個島嶼遍歷結束后更新，確保記錄的是“完整島嶼”的最大面積。
時間復雜度
| 操作類型 | 時間復雜度 | 說明 |
|---|---|---|
| 網格整體遍歷 | O(m×n) | 需通過雙重循環遍歷網格的每個單元格（共m×n個），檢查是否為未訪問的陸地 |
| DFS遞歸處理 | O(m×n) | 每個陸地單元格（1）最多被訪問一次（被標記為0后不再處理） |
| 面積計算與比較 | O(1) | 每個島嶼的面積累加（n++）和最大值更新（max(max_size, n)）均為常數操作 |
| 總計 | O(m×n) | m為網格行數，n為列數，整體時間由遍歷和遞歸的總操作數決定 |
補充說明：
- 時間復雜度的核心瓶頸是“網格遍歷”和“DFS遞歸”，兩者的總操作次數均與網格大小（m×n）成正比，因此整體復雜度為O(m×n)。
- 由于題目中網格規模較小（
m, n ≤ 50），即使是最壞情況（全為陸地），總操作次數也僅為50×50=2500次，DFS遞歸棧深度不會導致棧溢出，效率完全可控。
空間復雜度
| 消耗場景 | 空間復雜度 | 說明 |
|---|---|---|
| 遞歸調用棧（DFS） | O(m×n) | 最壞情況下（網格全為陸地，如 50×50 的全 1 網格），遞歸深度會達到網格總單元格數（m×n），此時棧空間消耗與網格規模成正比。 |
| 原地修改（無額外空間） | O(1) | 算法通過直接修改原網格（將訪問過的 1 改為 0）標記“已訪問”，未使用額外的數據結構（如哈希表、布爾數組），因此僅消耗常數級空間。 |
補充說明：
- 空間復雜度的瓶頸在于 DFS 的遞歸棧深度。由于題目中網格最大為
50×50，即使全為陸地，遞歸深度也僅為 2500，遠低于大多數編程語言的棧空間上限（通常為 104~105），因此不會出現棧溢出問題。 - 若改用 BFS 實現（用隊列存儲待訪問坐標），空間復雜度同樣為
O(m×n)（最壞情況下隊列會存儲所有陸地坐標），但避免了遞歸棧的限制，適合更大規模的網格場景。
四、與「島嶼數量」的代碼對比（一目了然看差異）
為了更清晰地看出兩道題的關系，我們用表格對比核心代碼：
| 功能點 | 島嶼數量（LeetCode 200） | 島嶼的最大面積（LeetCode 695） |
|---|---|---|
| 核心目標 | 統計島嶼的個數 | 統計最大島嶼的面積 |
| 關鍵變量 | sum（島嶼計數器） | n（當前島嶼面積）、max_size（最大面積） |
| 觸發搜索后操作 | sum++（每找到一個島嶼，計數器+1） | n=0 → 執行 DFS → max_size = max(...) |
| DFS 內部操作 | 僅標記陸地為 0，無額外計算 | 標記陸地為 0 后，執行 n++（累加面積） |
五、坑點總結
-
忘記重置
n：
如果在發現新島嶼時沒有將n重置為 0，會導致多個島嶼的面積累加在一起（比如前一個島嶼面積 3，后一個會從 3 開始加），結果錯誤。 -
max_size初始化錯誤：
若初始化為1而非0，當網格中沒有島嶼（全為0）時，會錯誤返回1而非0。 -
混淆
n和max_size的作用：
不要在遞歸過程中更新max_size，必須等一個島嶼完全遍歷結束后再更新——否則可能把不完整的面積當作最大值。
六、舉一反三
掌握了“計數”和“算面積”這兩種變體，你可以嘗試解決更復雜的連通區域問題：
- LeetCode 130. 被圍繞的區域：判斷哪些 ‘O’ 被 ‘X’ 完全包圍（從邊界的 ‘O’ 出發標記所有連通區域，未標記的 ‘O’ 則被包圍，需替換為 ‘X’）。
- LeetCode 1020. 飛地的數量：計算無法從邊界離開的陸地面積（在 DFS 基礎上增加“是否觸達邊界”的判斷）；
這些問題的核心依然是「Flood Fill 搜索框架」，只是在“統計目標”上做了微調——學會透過問題看本質，算法學習會事半功倍。
七、總結
今天的題目是「島嶼數量」的完美進階：它復用了相同的搜索邏輯，卻通過一個小小的目標變化（從“計數”到“算面積”），讓我們理解了如何在通用框架上進行靈活調整。
核心收獲：
- 復雜問題往往是簡單問題的變體，掌握基礎框架（如 DFS 遍歷連通區域）是關鍵；
- 解決“變體問題”時，重點關注目標的差異，并思考如何通過變量設計和流程調整來適配新目標。
如果對 DFS 的遞歸過程還不熟悉，建議回頭再看昨天題解中關于“遞歸拆解”的部分——基礎打牢了，再難的變體也能迎刃而解。
最后歡迎大家在評論區分享你的代碼或思路，咱們一起交流探討~ 🌟 要是有大佬有更精妙的思路或想法，懇請在評論區多多指點批評，我一定會虛心學習，并且第一時間回復交流噠！
這是封面原圖～ 喜歡的話先點個贊鼓勵一下唄～ 再順手關注一波，后續更新不迷路，保證讓你看得過癮！😉
)
