一【题目类别】

深度优先搜索

二【题目难度】

中等

三【题目编号】

695.岛屿的最大面积

四【题目描述】

给你一个大小为 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

六【解题思路】

此题比较简单，我们只需要按照深度优先搜索的模板去计算岛屿的最大面积即可：
- 遍历整个二维数组，如果遇到“1”，说明遇到一个岛屿，进入深度优先搜索
- 进入深度优先搜索后，如果不满足边界条件，就跳出深度优先搜索
- 然后将此区域置为“0”，表示已经搜索过了，然后记录岛屿个数
- 然后向四个方向搜索与当前岛屿连接的岛屿，并记录岛屿个数
- 最后将连接的所有岛屿个数返回
每次深度优先搜索返回的值都要与之前得到的值进行比较，我们保留最大的值，因为题目要求岛屿的最大面积
搜索完整个二维数组后，返回结果即可

七【题目提示】

m==grid.lengthm == grid.lengthm==grid.length
n==grid[i].lengthn == grid[i].lengthn==grid[i].length
1<=m,n<=501 <= m, n <= 501<=m,n<=50
grid[i][j]为0或1grid[i][j] 为 0 或 1grid[i][j]为0或1

八【时间频度】

时间复杂度：O(m∗n)O(m*n)O(m∗n)，其中m,nm,nm,n分别为传入的二维数组的行和列
空间复杂度：O(m∗n)O(m*n)O(m∗n)，其中m,nm,nm,n分别为传入的二维数组的行和列

九【代码实现】

Java语言版

class Solution {public int maxAreaOfIsland(int[][] grid) {int max = 0;for(int i = 0;ifor(int j = 0;jif(grid[i][j] == 1){max = Math.max(max,dfs(i,j,grid));}}}return max;}public int dfs(int i,int j,int[][] grid){if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){return 0;}grid[i][j] = 0;int count = 1;count += dfs(i + 1,j,grid);count += dfs(i,j + 1,grid);count += dfs(i - 1,j,grid);count += dfs(i,j - 1,grid);return count;}
}

C语言版

int dfs(int** grid,int i,int j,int row,int col)
{if(i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0){return 0;}grid[i][j] = 0;int count = 1;count += dfs(grid,i + 1,j,row,col);count += dfs(grid,i,j + 1,row,col);count += dfs(grid,i - 1,j,row,col);count += dfs(grid,i,j - 1,row,col);return count;
}int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize)
{int row = gridSize;int col = gridColSize[0];int res = 0;for(int i = 0;ifor(int j = 0;jres = fmax(res,dfs(grid,i,j,row,col));}}return res;
}

Python语言版

class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) -> int:def dfs(grid,i,j):if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:return 0grid[i][j] = 0count = 1count += dfs(grid,i + 1,j)count += dfs(grid,i,j + 1)count += dfs(grid,i - 1,j)count += dfs(grid,i,j - 1)return countres = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:res = max(res,dfs(grid,i,j))return res

C++语言版

class Solution {
public:int dfs(vector>& grid,int i,int j){if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0){return 0;}grid[i][j] = 0;int count = 1;count += dfs(grid,i + 1,j);count += dfs(grid,i,j + 1);count += dfs(grid,i - 1,j);count += dfs(grid,i,j - 1);return count;}int maxAreaOfIsland(vector>& grid) {int res = 0;for(int i = 0;ifor(int j = 0;jif(grid[i][j] == 1){res = max(res,dfs(grid,i,j));}}}return res;}
};