岛屿问题:三步走模板秒杀 8 道经典变体

哈喽，大家好呀，我是蔚蓝，今天我们来聊聊算法面试里的「岛屿问题」。

你有没有遇到过这种情况：刷 LeetCode 的时候，看到岛屿数量、最大面积、孤岛总面积这些题，感觉都差不多，但每次写都要重新想一遍逻辑，代码写得磕磕绊绊，面试的时候更是容易慌。

我之前也是这样。直到我发现，岛屿问题其实就是一套固定的「三步走」模板，掌握了这个模板，8 道经典变体都能秒杀。

岛屿问题是什么

给你一个二维网格，1 代表陆地，0 代表水。你要做的事情可能是：

  • 数有多少个岛屿
  • 找最大的岛屿面积
  • 计算岛屿周长
  • 沉没孤岛（不靠边界的岛）

这些题目看起来五花八门，但本质都是在网格上做 DFS/BFS 遍历。

为什么？

因为岛屿问题的核心就三个字：遍历、发现、扩散。

你遍历整个网格，发现一块陆地，然后从这块陆地出发，把所有相连的陆地都标记为「已访问」，这样就完成了一个岛屿的处理。

三步走模板

我把岛屿问题的解法总结成了一个「三步走」模板，记住这个模板，所有岛屿题都能套。

第一步：定义全局变量

1
2
3
4
static int row, col;           // 网格行列数
static int[][] grid;           // 网格数据
static boolean[][] visited;    // 访问标记
static int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};  // 四个方向

这四个变量是岛屿问题的「标配」，每道题都要用到。

dirs 数组存的是上下左右四个方向的偏移量，后面 DFS 的时候会用到。

第二步：定义 DFS 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void dfs(int x, int y) {
    // 1. 终止条件：越界 或 当前是海水 或 已访问
    if (x < 0 || x >= row || y < 0 || y >= col) return;
    if (grid[x][y] == 0 || visited[x][y]) return;

    // 2. 标记已访问
    visited[x][y] = true;

    // 3. 单层递归逻辑（根据题目变体调整）
    // - 染色：grid[x][y] = 2;
    // - 统计面积：count++;
    // - 统计周长：perimeter += 4 - neighbors;

    // 4. 向四个方向扩散
    for (int[] dir : dirs) {
        dfs(x + dir[0], y + dir[1]);
    }
}

DFS 函数的逻辑很清晰：

  1. 先判断终止条件（越界、是水、已访问）
  2. 标记当前位置为已访问
  3. 根据题目要求做具体操作（染色、统计面积、统计周长等）
  4. 向四个方向递归

这个模板是固定的，不同题目只需要调整第 3 步的逻辑。

第三步：遍历网格，进入 DFS

1
2
3
4
5
6
7
8
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (grid[i][j] == 1 && !visited[i][j]) {
            dfs(i, j);
            // 根据题目在此处更新答案
        }
    }
}

双重循环遍历整个网格，遇到陆地且未访问过，就进入 DFS。

有些题目需要在这里更新答案，比如岛屿数量就是每次进入 DFS 前 ans++。

💡 记忆口诀：全局变量开好头，终止条件先判断，标记扩散两手抓，双重循环遍网格

8 道经典变体

掌握了三步走模板，我们来看看 8 道经典变体怎么套用。

1. 岛屿数量

题目：给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的数量。

思路：遍历网格，遇到陆地时岛屿数量 +1，然后 DFS 标记所有相连的陆地。

1
2
3
4
5
6
7
8
9
int ans = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (!visited[i][j] && grid[i][j] == 1) {
            ans++;  // 发现新岛屿
            dfs(i, j);
        }
    }
}

注意：不要在调用 dfs 之前设置 visited[i][j] = true，这会导致 DFS 内部的检查直接返回。

2. 岛屿的最大面积

题目：计算岛屿的最大面积。

思路：在 DFS 时记录每个岛屿的面积，维护最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static int count;  // 记录当前岛屿面积

static void dfs(int x, int y) {
    if (x < 0 || x >= row || y < 0 || y >= col) return;
    if (visited[x][y] || grid[x][y] != 1) return;

    visited[x][y] = true;
    count++;  // 面积 +1

    for (int[] dir : dirs) {
        dfs(x + dir[0], y + dir[1]);
    }
}

// 主函数
int maxArea = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (!visited[i][j] && grid[i][j] == 1) {
            count = 0;  // 重置计数器
            dfs(i, j);
            maxArea = Math.max(maxArea, count);
        }
    }
}

3. 孤岛的总面积

题目：孤岛是那些完全不与矩阵边界接触的岛屿，计算所有孤岛的总面积。

思路：先从四条边界开始 DFS，将与边界相连的岛屿标记为「非孤岛」，然后统计剩余岛屿的面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Step 1: 将边界上的岛屿标记为已访问（非孤岛）
for (int i = 0; i < row; i++) {
    if (grid[i][0] == 1) dfs(i, 0);           // 左边界
    if (grid[i][col-1] == 1) dfs(i, col-1);   // 右边界
}
for (int j = 0; j < col; j++) {
    if (grid[0][j] == 1) dfs(0, j);           // 上边界
    if (grid[row-1][j] == 1) dfs(row-1, j);   // 下边界
}

// Step 2: 统计剩余岛屿的面积（真正的孤岛）
int totalArea = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (!visited[i][j] && grid[i][j] == 1) {
            count = 0;
            dfs(i, j);
            totalArea += count;
        }
    }
}

这道题的关键是「逆向思维」：先排除掉靠边界的岛屿，剩下的就是孤岛。

4. 沉没孤岛

题目：将所有孤岛（不与边界相连的岛屿）沉没，即将孤岛的 1 变为 0。

思路：

  1. 从四条边界开始 DFS，将与边界相连的岛屿标记为特殊值（如 2）
  2. 遍历整个网格：将 1 变为 0（沉没孤岛），将 2 变回 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Step 1: 标记边界岛屿为 2
for (int i = 0; i < row; i++) {
    if (grid[i][0] == 1) dfs(grid, i, 0);
    if (grid[i][col-1] == 1) dfs(grid, i, col-1);
}
for (int j = 0; j < col; j++) {
    if (grid[0][j] == 1) dfs(grid, 0, j);
    if (grid[row-1][j] == 1) dfs(grid, row-1, j);
}

// Step 2: 沉没孤岛，恢复边界岛屿
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (grid[i][j] == 1) grid[i][j] = 0;      // 沉没孤岛
        else if (grid[i][j] == 2) grid[i][j] = 1; // 恢复
    }
}

这道题和孤岛面积的思路类似，都是先处理边界，再处理内部。

5. 水流问题

题目：给定一个矩阵表示地形高度，水只能从高处流向低处或等高处。找出所有既能流向第一组边界（上边界和左边界）又能流向第二组边界（下边界和右边界）的单元格。

思路：逆向思维，从边界出发，逆向寻找能流向该边界的单元格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
boolean[][] first = new boolean[row][col];   // 能到达第一组边界
boolean[][] second = new boolean[row][col];  // 能到达第二组边界

// 从第一组边界（上、左）逆向搜索
for (int i = 0; i < row; i++) {
    dfs(grid, first, i, 0);  // 左边界
}
for (int j = 0; j < col; j++) {
    dfs(grid, first, 0, j);  // 上边界
}

// 从第二组边界（下、右）逆向搜索
for (int i = 0; i < row; i++) {
    dfs(grid, second, i, col-1);  // 右边界
}
for (int j = 0; j < col; j++) {
    dfs(grid, second, row-1, j);  // 下边界
}

// 统计同时能到达两组边界的单元格
int ans = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (first[i][j] && second[i][j]) {
            ans++;
        }
    }
}

注意 DFS 的逻辑要改成「逆向」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
    if (visited[x][y]) return;
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dirs[i][0];
        int ny = y + dirs[i][1];

        if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
            // 逆向：从边界往高处流
            if (grid[nx][ny] >= grid[x][y]) {
                dfs(grid, visited, nx, ny);
            }
        }
    }
}

这道题的关键是「逆向思维」：不是从高处往低处流，而是从边界往高处流。

6. 建造最大岛屿

题目：给定一个由 1（陆地）和 0（水）组成的矩阵，你可以将一个水单元格变为陆地，求能形成的最大岛屿面积。

思路：

  1. 第一次遍历：用不同编号（从 2 开始）标记每个岛屿，用 HashMap 记录每个编号对应的面积
  2. 第二次遍历：对每个水单元格，计算将其变为陆地后能连接的岛屿总面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Map<Integer, Integer> islandArea = new HashMap<>();
int mark = 2;
int maxArea = 0;

// Step 1: 标记岛屿并记录面积
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (grid[i][j] == 1) {
            count = 0;
            dfs(grid, i, j, mark);
            islandArea.put(mark, count);
            maxArea = Math.max(maxArea, count);  // 记录最大原始岛屿
            mark++;
        }
    }
}

// Step 2: 尝试填充每个水单元格
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (grid[i][j] == 0) {
            Set<Integer> neighborIslands = new HashSet<>();

            for (int k = 0; k < 4; k++) {
                int ni = i + dirs[k][0];
                int nj = j + dirs[k][1];

                if (ni >= 0 && ni < row && nj >= 0 && nj < col && grid[ni][nj] > 1) {
                    neighborIslands.add(grid[ni][nj]);
                }
            }

            int totalArea = 1;  // 当前填充的格子
            for (int islandMark : neighborIslands) {
                totalArea += islandArea.get(islandMark);
            }
            maxArea = Math.max(maxArea, totalArea);
        }
    }
}

注意：

  • 使用 Set 避免重复计算相邻的同一岛屿
  • 如果网格全是陆地（没有 0），答案就是最大原始岛屿面积

7. 岛屿的周长

题目：计算岛屿的周长。

思路一：遍历统计

  • 每个陆地单元格贡献 4 条边
  • 每对相邻的陆地单元格，减少 2 条边（因为共享边界）
  • 公式：周长 = 陆地数 × 4 - 相邻对数 × 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int landCount = 0;   // 陆地数量
int coverCount = 0;  // 相邻对数

for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (grid[i][j] == 1) {
            landCount++;
            // 只检查右边和下边，避免重复计算
            if (i + 1 < row && grid[i + 1][j] == 1) coverCount++;
            if (j + 1 < col && grid[i][j + 1] == 1) coverCount++;
        }
    }
}

System.out.println(landCount * 4 - coverCount * 2);

思路二：DFS 统计边界

在 DFS 过程中，遇到边界或水时，周长 +1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int perimeter;

static void dfs(int[][] grid, int x, int y) {
    // 遇到边界或水，周长 +1
    if (x < 0 || x >= row || y < 0 || y >= col) {
        perimeter++;
        return;
    }
    if (grid[x][y] == 0) {
        perimeter++;
        return;
    }
    if (grid[x][y] != 1) return;  // 已访问

    grid[x][y] = 2;  // 标记已访问

    for (int[] dir : dirs) {
        dfs(grid, x + dir[0], y + dir[1]);
    }
}

总结

岛屿问题的 8 道经典变体，核心都是「三步走」模板：

问题 核心思路
岛屿数量 遍历 + DFS 标记
最大面积 DFS 时记录面积
孤岛面积 先标记边界岛屿，再统计
沉没孤岛 边界岛屿标记为 2，1→0，2→1
水流问题 逆向 DFS，求交集
建造最大岛屿 编号标记 + HashMap + 遍历水格
岛屿周长 陆地×4 - 相邻×2 或 DFS 统计边界

通用技巧：

  • 方向数组：int[][] dirs = {{0,1}, {1,0}, {-1,0}, {0,-1}}
  • 边界检查：x < 0 || x >= row || y < 0 || y >= col
  • 标记已访问：visited[x][y] = true 或直接修改 grid[x][y] 的值

记住这个模板，面试的时候遇到岛屿问题，直接套就行了。

碎碎念

我最近在准备考研机试，刷了很多岛屿问题的题。一开始也是每道题都要重新想一遍，写得很慢。

后来我发现，这些题目的代码结构几乎一模一样，只是 DFS 里的逻辑稍微有点不同。于是我把这个「三步走」模板总结出来，现在遇到岛屿问题，基本上 5 分钟就能写完。

算法题不是靠死记硬背，而是要找到规律，提炼出模板。掌握了模板，你就能举一反三，遇到新题也不慌。

岛屿问题就是这样，掌握了三步走，8 道题都能秒。

希望这篇文章对你有帮助。如果你也在准备算法面试，可以把这个模板背下来，面试的时候直接套。

工具在变，模板不变。