日期：2026年10月16日
LeetCode 題目連結：695. Max Area of Island
解題想法
中等難度題。題目給一個 $m \times n$ 的二維陣列 $grid$，其中只有代表陸地的 $1$ 以及代表水域的 $0$，並且假設 $grid$ 四周都是 $0$。陸地可以往右、下、左、上等四個方向連接。要找出 $grid$ 之中面積最大的島嶼，也就是由最多的 $1$ 組成的連通區塊。連通區塊的題目，用 BFS 或 DFS 都可以解，由於我是以 Python 為主要的解題語言，我比較習慣用 BFS，如果用 DFS 經常會遇到遞迴深度過深的問題。這題我兩個方法都有寫，如果用 Python 解題 BFS 跑比較快，如果用 C++ 解題 DFS 跑比較快。
Python 程式碼
BFS. Runtime: 11 ms, beats 96.45%. Memory: 19.38 MB, beats 94.88%.
from collections import deque
class Solution:
def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
m, n, imax = len(grid), len(grid[0]), 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
continue
grid[i][j] = 0
area = 1
que = deque([(i, j)])
while que:
r, c = que.popleft()
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
area += 1
que.append((nr, nc))
imax = max(imax, area)
return imax
DFS. Runtime: 17 ms, beats 67.40%. Memory: 20.39 MB, beats 64.21%.
class Solution:
def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
m, n, imax = len(grid), len(grid[0]), 0
area = 0
# 自訂 dfs 函式，找連通區塊面積同時將走過的格子標記為 0
def dfs(r, c):
nonlocal area
area += 1
grid[r][c] = 0
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
dfs(nr, nc)
# 掃過每一格，跳過 0，遇到 1 呼叫 dfs
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
continue
# area 歸零之後再呼叫 dfs 找連通區塊面積
area = 0
dfs(i, j)
imax = max(imax, area)
return imax
C++ 程式碼
BFS. Runtime: 4 ms, beats 37.22%. Memory: 31.10 MB, beats 18.51%.
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = (int)grid.size(), n = (int)grid[0].size(), imax = 0;
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
grid[i][j] = 0;
int area = 1;
queue<pair<int, int>> que;
que.push({i, j});
while(!que.empty()) {
int r = que.front().first, c = que.front().second;
que.pop();
for(int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
area++;
que.push({nr, nc});
}
}
}
imax = max(imax, area);
}
}
return imax;
}
};
DFS. Runtime: 1 ms, beats 61.40%. Memory: 27.97 MB, beats 61.06%.
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = (int)grid.size(), n = (int)grid[0].size(), imax = 0;
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
grid[i][j] = 0;
int area = 1;
queue<pair<int, int>> que;
que.push({i, j});
while(!que.empty()) {
int r = que.front().first, c = que.front().second;
que.pop();
for(int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
area++;
que.push({nr, nc});
}
}
}
imax = max(imax, area);
}
}
return imax;
}
};
C 語言程式碼
BFS. Runtime: 6 ms, beats 2.82%. Memory: 11.41 MB, beats 14.08%.
#define max(a, b) ((a) > (b) ? (a) : (b))
typedef struct {
int r, c;
} Pos;
int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = *gridColSize, imax = 0;
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
grid[i][j] = 0;
int area = 1, head = 0, total = 1;
Pos que[2500]; // 上限為 50 * 50
que[0].r = i;
que[0].c = j;
while(head < total) {
int r = que[head].r, c = que[head].c;
head++;
for(int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
area++;
que[total].r = nr;
que[total].c = nc;
total++;
}
}
}
imax = max(imax, area);
}
}
return imax;
}
DFS. Runtime: 2 ms, beats 35.21%. Memory: 10.98 MB, beats 94.37%.
#define max(a, b) ((a) > (b) ? (a) : (b))
int m, n, imax, area;
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
int visited[50][50];
void dfs(int r, int c, int** grid) {
visited[r][c] = 1;
area++;
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && !visited[nr][nc]) {
dfs(nr, nc, grid);
}
}
}
int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize) {
m = gridSize; n = *gridColSize; imax = 0;
memset(visited, 0, sizeof(visited));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
area = 0;
dfs(i, j, grid);
imax = max(imax, area);
}
}
return imax;
}
沒有留言:
張貼留言