LeetCode算法日記 - Day 42: 島嶼數量、島嶼的最大面積

1. 島嶼數量

1.1 題目解析

1.2 解法

1.3 代碼實現

2.?島嶼的最大面積

2.1 題目解析

2.2 解法

2.3 代碼實現

1. 島嶼數量

https://leetcode.cn/problems/number-of-islands/

給你一個由?'1'（陸地）和?'0'（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網格的四條邊均被水包圍。

示例 1：

輸入：grid = [['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']
]
輸出：1

示例 2：

輸入：grid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']
]
輸出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]?的值為?'0'?或?'1'

1.1 題目解析

題目本質

在一個 m×n 的 0/1 網格上，統計由上下左右連通的“1”塊的個數；本質是“連通分量計數（四聯通）”。

常規解法

樸素想法：對每個為 ‘1’ 的格子啟動一次遍歷，把與之相連的 ‘1’ 都標記掉，然后計數 +1。遍歷可用 DFS 或 BFS。

問題分析

如果不做“訪問標記（vis）”，同一塊島嶼會被重復啟動遍歷 → 重復計數/超時。
如果標記時機不當（入隊后不立刻標記），同一坐標會被多次入隊 → 隊列暴漲。
邊界獲取不當（先取 grid[0].length 再判斷空矩陣）會 NPE。
復雜度：每格最多訪問一次，理想是 O(mn)；只要保證“入隊（或遞歸）前標記”為時機，就不會退化。

思路轉折

要高效、且不重算：
- 必須維護 vis[m][n] 訪問標記；
- 必須把標記動作放在“入隊/入棧前”；
- 必須只在遇到“未訪問的 ‘1’”時啟動一次 BFS/DFS，并在啟動點處給計數器 +1。
這樣“每個格子至多被處理一次”，時間 O(mn)、空間 O(mn)。

1.2 解法

算法思想

遍歷整個網格；每當遇到 grid[i][j]=='1' && !vis[i][j]：
- 啟動一輪 BFS；
- BFS 中用隊列彈出當前格，向四鄰擴展，對滿足邊界且為 ‘1’ 且未訪問的坐標：先標記 vis=true，再入隊；
- 該輪 BFS 結束后，說明整塊島嶼已被吞并，計數 ret++。

i）初始化

m = grid.length；若 m==0 直接返回 0。
n = grid[0].length；vis = new boolean[m][n]；ret = 0。

ii）掃描網格

雙層循環 (i,j)；當 grid[i][j]=='1' && !vis[i][j] 時，啟動 BFS(i,j)。

iii）BFS 過程

隊列入起點 (si,sj)，立刻標記 vis[si][sj]=true。
不斷出隊 (a,b)，向四方向 (a+dx[k], b+dy[k]) 擴展；滿足：
- 在邊界內、
- 未訪問、
- 且為 ‘1’
  → 先標記再入隊。
- 隊列清空即該島處理完畢，ret++。

iiii）返回 ret。

易錯點

n = grid[0].length 必須放在 m==0 判空之后，否則空矩陣會 NPE。
if (grid[i][j]=='1' && !vis[i][j]) 中的 !vis[i][j] 一開始當然都是 true，但第一輪 BFS 會把整塊島都標記為 true，后續再遇到同島格子就不會重復啟動 BFS。
標記時機要在入隊前/時，否則同一坐標可能被多次入隊。
只統計“第一次發現這塊島”的那一刻（啟動 BFS 時）的一次 ret++
注意字符比較用 '1'，不要寫成 1。
四方向遍歷下標不要寫錯。
不要重復無意義的標記（出隊后再次 vis[a][b]=true 屬于冗余）。

1.3 代碼實現

import java.util.*;class Solution {int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;Queue<int[]> q = new LinkedList<>();boolean[][] vis;int ret;public int numIslands(char[][] grid) {m = grid.length;if (m == 0) return 0;            // 先判空，再取 nn = grid[0].length;vis = new boolean[m][n];ret = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1' && !vis[i][j]) {bfs(grid, i, j);    // 一次 BFS 吞并一整塊島}}}return ret;}// BFS：以 (si, sj) 為起點吞并整塊島嶼public void bfs(char[][] grid, int si, int sj) {q.clear();                       // 成員隊列：顯式清空更穩妥q.offer(new int[]{si, sj});vis[si][sj] = true;              // 入隊前/時標記，避免重復入隊while (!q.isEmpty()) {int[] cur = q.poll();int a = cur[0], b = cur[1];for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n&& !vis[x][y] && grid[x][y] == '1') {vis[x][y] = true;     // 先標記，再入隊q.offer(new int[]{x, y});}}}ret++;                            // 本輪 BFS 結束 → 發現了一座島}
}

復雜度分析

時間復雜度：O(m·n)，每個格子最多被入隊/出隊一次，四鄰檢查是常數。
空間復雜度：O(m·n)，主要在 vis；隊列最壞可能裝下整層邊界上的若干格子，但受 O(mn) 上界。

2.?島嶼的最大面積

https://leetcode.cn/problems/max-area-of-island/

給你一個大小為?m x n?的二進制矩陣?grid?。

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

島嶼的面積是島上值為?1?的單元格的數目。

計算并返回?grid?中最大的島嶼面積。如果沒有島嶼，則返回面積為?0?。