695. 岛屿的最大面积
695. 岛屿的最大面积
🟠 🔖 深度优先搜索
广度优先搜索
并查集
数组
矩阵
🔗 力扣
LeetCode
题目
You are given an m x n
binary matrix grid
. An island is a group of 1
's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1
in the island.
Return _the maximumarea of an island in _grid
. If there is no island, return 0
.
Example 1:
Input: 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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j]
is either0
or1
.
题目大意
给你一个大小为 m x n
的二进制矩阵 grid
。
岛屿 是由一些相邻的 1
(代表土地) 构成的组合,这里的「相邻」要求两个 1
必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid
的四个边缘都被 0
(代表水)包围着。
岛屿的面积是岛上值为 1
的单元格的数目。
计算并返回 grid
中最大的岛屿面积。如果没有岛屿,则返回面积为 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
解释: 答案不应该是 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]
为0
或1
解题思路
这道题和 第 200 题 岛屿数量 的解题思路是一样的,只不过需要给 dfs 函数加一个返回值,记录岛屿的面积。
遍历整个网格,并在每次找到一个陆地单元时,使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历所有相连的陆地单元,从而将整个岛屿标记为已访问。
- 遍历网格:遍历每一个单元格,如果当前单元格是
'1'
(陆地),则找到一个新的岛屿,计数器加一。 - 标记已访问:使用 DFS 从当前单元格开始,标记所有连通的陆地单元为
'0'
(水),表示它们已被访问,并返回岛屿面积。 - 继续遍历:继续遍历剩余的单元格,直到整个网格被检查完。
复杂度分析
- 时间复杂度:
O(m * n)
,其中m
是网格的行数,n
是网格的列数,每个格子最多会被访问一次。 - 空间复杂度:
O(m * n)
,最坏情况下,递归的深度可能达到m * n
,因此递归调用栈的空间复杂度为O(m * n)
代码
/**
* @param {number[][]} grid
* @return {number}
*/
var maxAreaOfIsland = function (grid) {
const m = grid.length,
n = grid[0].length;
// 从 (i, j) 开始,将与之相邻的陆地都变成海水
const dfs = (grid, i, j) => {
// 超出索引边界
if (i < 0 || j < 0 || i >= m || j >= n) {
return 0;
}
// (i, j) 已经是海水了
if (grid[i][j] == 0) return 0;
// 将 (i, j) 变成海水
grid[i][j] = 0;
// // 淹没上下左右的陆地,并返回相邻岛屿面积
return (
dfs(grid, i - 1, j) +
dfs(grid, i + 1, j) +
dfs(grid, i, j - 1) +
dfs(grid, i, j + 1) +
1
);
};
let res = 0;
// 遍历 grid
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] == 1) {
// 记录最大岛屿面积
res = Math.max(res, dfs(grid, i, j));
}
}
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
200 | 岛屿数量 | [✓] | 深度优先搜索 广度优先搜索 并查集 2+ | |
419 | 棋盘上的战舰 | 深度优先搜索 数组 矩阵 | ||
463 | 岛屿的周长 | 深度优先搜索 广度优先搜索 数组 1+ | ||
1727 | 重新排列后的最大子矩阵 | 贪心 数组 矩阵 1+ | ||
2101 | 引爆最多的炸弹 | 深度优先搜索 广度优先搜索 图 3+ |