题目难度: 中等
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1:
- 输入: 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]]
- 输出: 6
- 解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
- 输入: grid = [[0,0,0,0,0,0,0,0]]
- 输出: 0
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0 or 1
题目思考
- 如何得到哪些土地相互连通?
解决方案
- 分析题目, 不难发现这道题的核心在于求连通分量, 所以我们可以采用经典的 BFS 算法:
- 遍历所有格子, 如果当前格子是尚未访问的土地, 则从它开始向上下左右四个方向扩散, 找相邻的土地
- 然后将访问过的土地格子都标记为已访问, 直到这些点都处理完毕
- 此时遍历的格子数目即为当前岛屿大小
- 相比传统的 BFS, 我们这里可以做出一些改进, 从而做到不需要使用额外的 visit 集合来判断哪些点已经被遍历过
- 具体做法是: 访问过某个土地格子后, 就将其值改为 0, 说白了就是将原有土地变成水, 这样就不会再次处理它
- 最终结果就是所有岛屿大小的最大值
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(RC): R 和 C 是矩阵的行和列数, 每个格子只需要访问常数次 (判断或填充) - 空间复杂度
O(1): 只使用了常数空间的变量
代码
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
# BFS+原地更改
rows, cols = len(grid), len(grid[0])
res = 0
for sr in range(rows):
for sc in range(cols):
if grid[sr][sc] == 1:
# 找到一个尚未遍历过的土地, 开始BFS
q = [(sr, sc)]
# 将原有土地变成水, 更改其值为0, 避免重复遍历
grid[sr][sc] = 0
for r, c in q:
for rr, cc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
# 判断4个方向的相邻格子
if 0 <= rr < rows and 0 <= cc < cols and grid[rr][cc] == 1:
# 当前相邻格子也是土地, 属于岛屿的一部分
q.append((rr, cc))
# 同样将其值改为0, 避免重复遍历
grid[rr][cc] = 0
# 最后队列q的长度即为当前岛屿大小, 取最大值作为最终结果
res = max(res, len(q))
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号