LeetCode 463. 岛屿的周长

2025-10-10 HGNULB 约 6 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 463. 岛屿的周长

题意分析

输入是一个只含 0 和 1 的矩形网格，1 是陆地格，0 是水格，每个格子都是边长为 1 的正方形。要输出的是陆地区域的轮廓总长度。

题目给了几条很强的约束：格子之间只按上下左右四个方向相邻；网格恰好只有一个岛屿；岛内没有湖，也就是不存在被陆地包围的水域。前两条保证不用做连通性判断，最后一条保证不用区分内轮廓和外轮廓——所有暴露在外的边都属于同一条周长。

换个角度看，「周长」就是「陆地格与水格之间的分界线条数」，再加上贴着网格边界的那些边。这个等价说法把几何问题变成了纯粹的计数问题。

边界上要注意：位于第一行、第一列、最后一行、最后一列的陆地格，它们朝向网格外侧的边同样计入周长；网格里可能一块陆地都没有，此时周长为 0。

解法：统计陆地和相邻边

核心思路

最直白的做法是对每个陆地格看四个方向：某个方向越界或者是水，就给周长加 1。这已经是 $O(mn)$ 了，正确也够快，但每个格子要写四次边界判断，白板上很容易漏掉某个方向。

换一个记账方式：先假设每块陆地都是孤立的，那么它贡献 4 条边。接着修正——两块陆地上下或左右贴在一起时，它们之间那条边被双方各自算了一次，实际却不在轮廓上，所以要从总数里扣掉 2。

于是问题变成「数出有多少对相邻的陆地」。为了不把同一对数两次，扫描时只往回看：对当前陆地格，只检查它的上方和左方。因为按从上到下、从左到右的顺序遍历，任意一对相邻陆地中，靠后的那一个一定能在自己的上方或左方看到靠前的那一个，且只会看到一次。

正确性可以直接从边的贡献证明：设陆地格数量为 $L$，相邻陆地对数量为 $A$。所有陆地先贡献 $4L$；每对相邻陆地共享一条边，这条边在 $4L$ 中被算了两次，但对周长的真实贡献为 0，因此每对要减 2，最终周长就是 $4L - 2A$。只看上、左恰好把每个相邻对计数一次，所以算法不会漏算或重复扣减。

解题步骤

把答案初始化为 0，按行、再按列遍历每个格子。固定这个顺序是后面「只看上和左」能成立的前提。

遇到水格直接跳过，它不贡献任何轮廓。

遇到陆地格先把答案加 4，先按孤立格记账，后面再做修正。

若行号大于 0 且正上方是陆地，答案减 2。减 2 而不是 1，是因为这条公共边在双方各自的 4 条里都被算过一次。

若列号大于 0 且正左方是陆地，答案减 2，理由同上。只查上、左两个方向，保证每一对相邻陆地恰好被扣一次。

遍历结束后返回答案。

以 grid = [[1,1],[1,0]] 为例：共有 3 块陆地，先贡献 $3 \times 4 = 12$；(0,1) 与左侧相邻、(1,0) 与上侧相邻，共 2 对，每对扣 2，得到 $12 - 2 \times 2 = 8$。这个小例子同时覆盖水平相邻、垂直相邻和凹角，适合在面试中快速验证公式。

代码实现

class Solution {
    public int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 0) {
                    continue;
                }
                perimeter += 4;
                if (row > 0 && grid[row - 1][col] == 1) {
                    perimeter -= 2;
                }
                if (col > 0 && grid[row][col - 1] == 1) {
                    perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
}

func islandPerimeter(grid [][]int) int {
    perimeter := 0
    for row := 0; row < len(grid); row++ {
        for col := 0; col < len(grid[0]); col++ {
            if grid[row][col] == 0 {
                continue
            }
            perimeter += 4
            if row > 0 && grid[row-1][col] == 1 {
                perimeter -= 2
            }
            if col > 0 && grid[row][col-1] == 1 {
                perimeter -= 2
            }
        }
    }
    return perimeter
}

复杂度分析

时间复杂度：$O(mn)$，m、n 为网格的行数与列数；每个格子只被访问一次，格内做常数次判断。

空间复杂度：$O(1)$，只用一个累加变量，不需要访问标记数组，也没有递归栈。

关键点总结

面积类问题看「格子数」，周长类问题看「格子与外界的分界」。把周长重述成「陆地与水或边界之间的边数」，几何问题立刻变成计数问题。

先按最简情形整体记账、再统一扣除重复计入的部分，是计数题的通用套路，比逐项分类讨论更不容易漏。

为每个维度只选一个方向（本实现选上、左），就能让每对相邻陆地恰好被处理一次；选择上、右或下、左也正确，但边界判断要随之调整。

题目保证只有一个岛且岛内无湖，所以不需要连通性遍历；一旦去掉这个保证（比如要求「主岛周长」），就必须先用 DFS 或 BFS 定位目标连通块。

面试时先给出逐边判断，再推导 $4L - 2A$，能清楚展示从定义到计数公式的优化过程；本题不需要 DFS，使用遍历计数更直接。

易错点总结

错误写法：对上下左右四个方向都做「是陆地就减 2」→ grid = [[1,1]]：两块陆地各自减一次，答案变成 $4 + 4 - 2 - 2 = 4$，正确答案是 6。同一对相邻被扣了两次。

错误写法：相邻时只减 1 → [[1,1]] 得 $8 - 1 = 7$，正确答案是 6。公共边在双方的「4 条」里各被算了一次，必须扣 2。

错误写法：省略 row > 0、col > 0 的下标检查 → grid = [[1]]：访问 grid[-1][0] 直接越界抛异常。

错误写法：用 grid[0].length 之外的列数（比如误用 grid.length）控制内层循环 → 非正方形网格如 [[1,0,0]] 会漏扫或越界，前者少算周长，后者直接崩。

错误写法：横向看左和右、纵向却只看上 → 水平相邻对会被扣两次，垂直相邻对只扣一次；每个维度都必须恰好选择一个方向。

错误写法：只有陆地格在网格内部才加 4 → [[1]] 会得到 0，正确答案是 4；贴着网格边界的边同样属于岛屿周长。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	数连通块个数，必须遍历并标记访问
695. 岛屿的最大面积	中等	求单个连通块的格子数最大值，DFS 需要带返回值累加
130. 被围绕的区域	中等	从边界反向染色，原地改写网格
1020. 飞地的数量	中等	统计无法走到边界的陆地，同样是边界反向淹没
1254. 统计封闭岛屿的数目	中等	判断连通块是否完全不接触边界
694. 不同岛屿的数量	中等	需要把形状序列化去重，考察遍历路径的编码
LCR 105. 岛屿的最大面积	中等	与 695 同题，可用并查集维护连通块大小
面试题 16.19. 水域大小	中等	八方向连通，且需要把所有面积排序输出