0695. 岛屿的最大面积 #
- 标签:搜索
- 难度:中等
题目大意 #
描述:给定一个只包含 0
、1
元素的二维数组,1
代表岛屿,0
代表水。一座岛的面积就是上下左右相邻的 1
所组成的连通块的数目。
要求:计算出最大的岛屿面积。
说明:
- $m == grid.length$。
- $n == grid[i].length$。
- $1 \le m, n \le 50$。
- $grid[i][j]$ 为
0
或1
。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:深度优先搜索 #
- 遍历二维数组的每一个元素,对于每个值为
1
的元素:- 将该位置上的值置为
0
(防止二次重复计算)。 - 递归搜索该位置上下左右四个位置,并统计搜到值为
1
的元素个数。 - 返回值为
1
的元素个数(即为该岛的面积)。
- 将该位置上的值置为
- 维护并更新最大的岛面积。
- 返回最大的到面积。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times m)$,其中 $m$ 和 $n$ 分别为行数和列数。
- 空间复杂度:$O(n \times m)$。
思路 2:广度优先搜索 #
- 使用
ans
记录最大岛屿面积。 - 遍历二维数组的每一个元素,对于每个值为
1
的元素:- 将该元素置为
0
。并使用队列q
存储该节点位置。使用temp_ans
记录当前岛屿面积。 - 然后从队列
q
中取出第一个节点位置(i, j)
。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为0
(避免重复搜索)。并将其加入到队列中。并累加当前岛屿面积,即temp_ans += 1
。 - 不断重复上一步骤,直到队列
q
为空。 - 更新当前最大岛屿面积,即
ans = max(ans, temp_ans)
。
- 将该元素置为
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n \times m)$,其中 $m$ 和 $n$ 分别为行数和列数。
- 空间复杂度:$O(n \times m)$。