題目描述:給定一個由 0(水)和 1(陸地)組成的二維網格,找出面積最大的島嶼並回傳其面積。島嶼是由四方向(上下左右)相連的 1 所構成的區域,網格邊界外視為水。
解題思路:對每個未訪問的 1 格,啟動一次 DFS/BFS 計算該島嶼的面積,同時將已訪問的格子設為 0 以避免重複計算(原地標記)。遍歷所有格子,追蹤所有島嶼中的最大面積。DFS 的遞迴方式最為簡潔:每訪問一格就回傳 1 + DFS(四個鄰居),若格子越界或為水則回傳 0。
時間複雜度:O(m × n) — 每個格子最多被訪問一次,m 和 n 分別為網格的行數與列數。
空間複雜度:O(m × n) — 最壞情況下遞迴呼叫堆疊深度為整個網格大小(全為陸地時)。若使用迭代 BFS,空間同為 O(m × n) 用於佇列。
1. Define dfs(grid, r, c): a. If out of bounds or grid[r][c] == 0: return 0 b. Set grid[r][c] = 0 (mark visited) c. Return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1) 2. Initialize maxArea = 0 3. For each cell (r, c) in grid: a. If grid[r][c] == 1: maxArea = max(maxArea, dfs(grid, r, c)) 4. Return maxArea
BFS 迭代法 O(m×n):對每個未訪問的 1 格,使用佇列進行廣度優先搜尋,逐層擴展並計算面積。避免遞迴堆疊溢出,適合超大網格。
Union-Find O(m×n × α(m×n)):將每個 1 格視為節點,合併四方向相鄰的 1 格,最後找出最大連通分量的大小。實作較複雜,但在動態新增陸地的場景下更具彈性。