LeetCode 463. 岛屿的周长
题目描述
题意分析
网格中的陆地通过上下左右相连，组成唯一一个没有湖泊的岛屿。每个格子的边长为 1，要求陆地与水域相接的边长总和；网格外也视为水域，所以贴着网格边界的陆地边同样计入周长。
解法：统计陆地和相邻边
核心思路
[!blue]
先把每个陆地格当成独立的小岛，各贡献四条边。这样，陆地与水域相接的边恰好计入一次，而两个陆地格之间的共享边会从两侧各计入一次。共享边不属于周长，必须把这两份都扣掉。因此答案就是陆地格数乘 4，再减去共享边数乘 2。
为了让每条共享边只扣一次，每个陆地格只检查上方和左方：竖直相邻的一对由下面的格子处理，水平相邻的一对由右边的格子处理。所有共享边都会被覆盖，也不会重复扣除；水域和网格外侧没有相邻陆地，无需扣减，便自然留下了周长。
整个过程只读取网格并累加结果，不需要搜索岛屿、修改陆地标记或维护访问数组。
解题步骤
- 遍历全部行和列，跳过水格。
- 陆地先加四。
- 上方是陆地减二，左方是陆地也减二。
- 全部格子处理完成后，返回累计周长。
代码实现
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)$，只保存累计值与下标。
关键点总结
[!green]
- 共享边按两份扣除。
- 只选每个维度的一个方向统计相邻对。
- 第一行没有上方格子，第一列没有左方格子；先检查下标边界，外侧的边就会正常保留。
易错点总结
[!yellow]
- 四方向都减二，会把共享边重复扣除。
- 只减一，会留下本应删除的另一份共享边。
- 列循环误用行数，会漏扫或越界；题目保证网格为非空矩形，列数应取
grid[0]的长度。- 对角线接触不构成共享边，不能扣减周长。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！