695. Max Area of Island
MediumDescription
給定一個
m x n的二進位矩陣grid，其中1代表陸地、0代表水域。回傳最大島嶼的面積（相連的1的數量）。若沒有島嶼則回傳0。
Example:
Input: 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]] Output: 6
Intuition#
和 Number of Islands 相同框架，DFS/BFS 遍歷時累計面積，取最大值。
- 遍歷網格，對每個
1啟動 DFS/BFS 計算該島嶼面積 - 維護一個全域最大值，每次比較更新
- 原地標記避免重複訪問
Approaches#
1: BFS#
- 概念: 用 BFS 遍歷每座島嶼，累計面積並更新最大值
- 時間複雜度:
O(m * n) - 空間複雜度:
O(min(m, n))
class Solution {
fun maxAreaOfIsland(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
var maxArea = 0
val dirs = intArrayOf(0, 1, 0, -1, 0)
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 1) {
var area = 0
val queue: ArrayDeque<Int> = ArrayDeque()
grid[i][j] = 0
queue.add(i * n + j)
while (queue.isNotEmpty()) {
val cur = queue.removeFirst()
area++
val r = cur / n
val c = cur % n
for (d in 0 until 4) {
val nr = r + dirs[d]
val nc = c + dirs[d + 1]
if (nr in 0 until m && nc in 0 until n && grid[nr][nc] == 1) {
grid[nr][nc] = 0
queue.add(nr * n + nc)
}
}
}
maxArea = maxOf(maxArea, area)
}
}
}
return maxArea
}
}⭐2: DFS（遞迴）#
- 概念: 遞迴 DFS 回傳每座島嶼面積，程式碼最簡潔
- 時間複雜度:
O(m * n) - 空間複雜度:
O(m * n)（遞迴堆疊最壞情況）
class Solution {
fun maxAreaOfIsland(grid: Array<IntArray>): Int {
var maxArea = 0
for (i in grid.indices) {
for (j in grid[0].indices) {
if (grid[i][j] == 1) {
maxArea = maxOf(maxArea, dfs(grid, i, j))
}
}
}
return maxArea
}
private fun dfs(grid: Array<IntArray>, i: Int, j: Int): Int {
if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] != 1) return 0
grid[i][j] = 0
return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1)
}
}🔑 Takeaways#
- Pattern: 網格連通性 + 面積計算 – DFS 回傳值累加
- 關鍵技巧: DFS 函數回傳面積值，比用全域變數更乾淨；和 200. Number of Islands 是同一模板的變體