• 力扣第695题 岛屿的最大面积 C++ DFS BFS 附Java代码


    题目

    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
    
    

    提示:

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

    思路和解题方法 1 DFS

    1. dfs 函数通过传入的坐标 (x, y) 来探索当前陆地区域的情况。如果当前坐标越界(超出了网格范围)或者是海洋(值为 0),则返回面积 0,表示此处不是陆地。

    2. 如果当前坐标是陆地(值为 1),则将其标记为已访问过(即将值置为 0),以免重复访问同一块陆地。然后开始向当前位置的上、下、左、右四个方向进行深度优先搜索,探索与当前陆地相连的其他陆地。

    3. 在每一步深度优先搜索中,我们累加当前陆地的面积,并递归地探索相邻的陆地。这样,通过深度优先搜索,我们能够计算出以当前位置为起点的整个连通陆地区域的面积。

    4. 最后,将累计的面积作为返回值返回给上一级递归调用。

    maxAreaOfIsland 函数中,我们遍历整个网格,对于每个岛屿的起始位置(即值为 1 的位置),调用 dfs 函数来计算以该位置为起点的岛屿的面积。并将得到的面积与当前记录的最大面积进行比较,并更新最大面积的值。

    时间复杂度分析:

    • 对于每个格子,最坏情况下需要进行深度优先搜索,而深度优先搜索的时间复杂度是 O(m*n),其中 m 和 n 分别为 grid 的行数和列数。
    • 因此,总的时间复杂度为 O(m*n),其中 m 为 grid 的行数,n 为 grid 的列数。

    空间复杂度分析:

    • 深度优先搜索过程中使用的递归调用栈的最大深度为岛屿的大小,最坏情况下为整个 grid 大小,因此空间复杂度为 O(m*n)。
    • 此外,还需要考虑输入参数和一些辅助变量的空间占用,但是这些空间占用都是常数级别的,因此不影响总体的空间复杂度。

    综上所述,该算法的时间复杂度为 O(mn),空间复杂度也为 O(mn)。

    c++ 代码

    1. class Solution {
    2. public:
    3. // 深度优先搜索函数,用于搜索连通的岛屿区域并返回面积
    4. int dfs(vectorint>>& grid, int x, int y) {
    5. // 递归终止条件
    6. if (x < 0 || x == grid.size() || y < 0 || y == grid[0].size() || grid[x][y] == 0) return 0;
    7. grid[x][y] = 0; // 将已经搜索过的陆地置为0,防止重复搜索(即将其视为沉没的岛屿)
    8. int ans = 1;
    9. // 分别搜索当前陆地的上、下、右、左四个方向的区块
    10. ans += dfs(grid, x, y + 1); // 上面
    11. ans += dfs(grid, x, y - 1); // 下面
    12. ans += dfs(grid, x + 1, y); // 右边
    13. ans += dfs(grid, x - 1, y); // 左边
    14. return ans; // 返回当前连通岛屿的总面积
    15. }
    16. // 计算最大岛屿面积的函数
    17. int maxAreaOfIsland(vectorint>>& grid) {
    18. int ans = 0; // 初始化最大面积为0
    19. for (int i = 0; i != grid.size(); ++i) {
    20. for (int j = 0; j != grid[0].size(); ++j) {
    21. if (grid[i][j] == 1) { // 如果当前位置是陆地
    22. int cnt = dfs(grid, i, j); // 对当前的岛屿区域进行深度优先搜索,得到面积
    23. ans = max(ans, cnt); // 更新最大面积
    24. }
    25. }
    26. }
    27. return ans; // 返回最大岛屿面积
    28. }
    29. };

    思路和解题方法 2 BFS

    1. 首先,定义了一个类 Solution,其中包含了一个公有函数 maxAreaOfIsland,该函数接收一个二维向量 grid 作为参数,并返回岛屿的最大面积。

    2. maxAreaOfIsland 函数中,我们首先初始化 ans 为 0,以便记录最大的岛屿面积。

    3. 接下来是两个嵌套的 for 循环,用来遍历整个二维网格 grid

    4. 在每次迭代中,我们首先初始化 cur 为 0,用于记录当前岛屿的面积。然后创建两个队列 queueiqueuej,用于存储待访问的陆地坐标。

    5. 将当前遍历到的位置 (i, j) 入队,即将它们分别加入到 queueiqueuej 中。

    6. 进入while循环,只要队列非空,就不断进行以下操作:

      • 弹出队首的坐标 (cur_i, cur_j)
      • 检查当前坐标是否越界或者不是陆地,若是则跳过本次循环;
      • 若当前坐标是陆地,则将当前面积 cur 自增,并将当前坐标标记为已访问过的海洋(即将值置为 0),然后探索当前位置的上、下、左、右四个方向;
      • 将相邻的陆地坐标入队。
    7. 在每次内部循环结束时,更新 ans 为当前 curans 之间的较大值。

    8. 最后,遍历结束后返回 ans,即为岛屿的最大面积。

    时间复杂度分析:

    • 时间复杂度取决于岛屿的数量和网格的大小。假设网格的行数为 m,列数为 n,岛屿的数量为 k,那么时间复杂度可以表示为 O(mn+k),其中 mn 表示遍历整个网格的时间复杂度,k 表示计算岛屿面积的时间复杂度。

    空间复杂度分析:

    • 空间复杂度方面,使用了两个队列 queueiqueuej,它们的最大长度可以达到网格的面积大小,因此空间复杂度也是 O(m*n)。

    综上所述,该算法的时间复杂度为 O(mn),空间复杂度也为 O(mn)。

    c++ 代码

    1. class Solution {
    2. public:
    3. int maxAreaOfIsland(vectorint>>& grid) {
    4. int ans = 0;
    5. // 遍历二维网格的每一个位置
    6. for (int i = 0; i != grid.size(); ++i) {
    7. for (int j = 0; j != grid[0].size(); ++j) {
    8. int cur = 0; // 当前岛屿的面积
    9. queue<int> queuei;
    10. queue<int> queuej;
    11. queuei.push(i); // 将当前位置加入队列
    12. queuej.push(j);
    13. while (!queuei.empty()) {
    14. int cur_i = queuei.front(), cur_j = queuej.front(); // 取出队首元素
    15. queuei.pop();
    16. queuej.pop();
    17. if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
    18. continue; // 如果当前位置超出边界或者不是岛屿,跳过
    19. }
    20. ++cur; // 当前岛屿面积加一
    21. grid[cur_i][cur_j] = 0; // 将当前位置置为0,表示已经访问过
    22. int di[4] = {0, 0, 1, -1}; // 方向数组,表示上下左右四个方向
    23. int dj[4] = {1, -1, 0, 0};
    24. for (int index = 0; index != 4; ++index) {
    25. int next_i = cur_i + di[index], next_j = cur_j + dj[index]; // 计算四个相邻位置
    26. queuei.push(next_i); // 将相邻位置加入队列
    27. queuej.push(next_j);
    28. }
    29. }
    30. ans = max(ans, cur); // 更新最大岛屿面积
    31. }
    32. }
    33. return ans; // 返回最大岛屿面积
    34. }
    35. };

    附Java代码

    DFS

    1. class Solution {
    2. public int maxAreaOfIsland(int[][] grid) {
    3. int ans = 0; // 初始化最大岛屿面积为0
    4. for (int i = 0; i != grid.length; ++i) { // 遍历二维网格的每一个位置
    5. for (int j = 0; j != grid[0].length; ++j) {
    6. ans = Math.max(ans, dfs(grid, i, j)); // 计算以当前位置为起点的岛屿面积,并更新最大值
    7. }
    8. }
    9. return ans; // 返回最大岛屿面积
    10. }
    11. public int dfs(int[][] grid, int cur_i, int cur_j) {
    12. if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
    13. return 0; // 如果当前位置超出边界或者不是岛屿,返回面积为0
    14. }
    15. grid[cur_i][cur_j] = 0; // 将当前位置置为0,表示已经访问过
    16. int[] di = {0, 0, 1, -1}; // 方向数组,表示上下左右四个方向
    17. int[] dj = {1, -1, 0, 0};
    18. int ans = 1; // 当前岛屿面积初始化为1
    19. for (int index = 0; index != 4; ++index) {
    20. int next_i = cur_i + di[index], next_j = cur_j + dj[index]; // 计算四个相邻位置
    21. ans += dfs(grid, next_i, next_j); // 递归计算相邻位置的岛屿面积并累加
    22. }
    23. return ans; // 返回当前岛屿面积
    24. }
    25. }

    BFS

    1. class Solution {
    2. // 计算岛屿的最大面积
    3. public int maxAreaOfIsland(int[][] grid) {
    4. int ans = 0; // 初始化最大面积为 0
    5. // 遍历整个网格
    6. for (int i = 0; i != grid.length; ++i) {
    7. for (int j = 0; j != grid[0].length; ++j) {
    8. int cur = 0; // 当前岛屿的面积
    9. Queue queuei = new LinkedList(); // 存储陆地坐标的队列
    10. Queue queuej = new LinkedList(); // 存储陆地坐标的队列
    11. queuei.offer(i); // 将当前坐标入队
    12. queuej.offer(j); // 将当前坐标入队
    13. // BFS 遍历岛屿
    14. while (!queuei.isEmpty()) {
    15. int cur_i = queuei.poll(), cur_j = queuej.poll(); // 出队当前坐标
    16. // 检查当前坐标是否越界或者不是陆地,若是则跳过本次循环
    17. if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
    18. continue;
    19. }
    20. ++cur; // 当前岛屿的面积加一
    21. grid[cur_i][cur_j] = 0; // 标记当前坐标为已访问过的海洋
    22. int[] di = {0, 0, 1, -1}; // 方向数组,分别表示上、下、左、右四个方向
    23. int[] dj = {1, -1, 0, 0}; // 方向数组,分别表示上、下、左、右四个方向
    24. // 探索当前位置的上、下、左、右四个方向
    25. for (int index = 0; index != 4; ++index) {
    26. int next_i = cur_i + di[index], next_j = cur_j + dj[index]; // 计算相邻坐标
    27. queuei.offer(next_i); // 将相邻的陆地坐标入队
    28. queuej.offer(next_j); // 将相邻的陆地坐标入队
    29. }
    30. }
    31. ans = Math.max(ans, cur); // 更新最大面积
    32. }
    33. }
    34. return ans; // 返回岛屿的最大面积
    35. }
    36. }

    觉得有用的话可以点点赞,支持一下。

    如果愿意的话关注一下。会对你有更多的帮助。

    每天都会不定时更新哦  >人<  。

  • 相关阅读:
    解决electron + react单页应用调用localhost服务失败
    nginx实现负载均衡load balance
    加持智慧医疗,美格智能5G数传+智能模组让就医触手可及
    【 数据分析概述与职业操守】——CDA level1
    【Iceberg+Alluxio】助力加速数据通道(下篇)
    扩散模型的启发和因果推论之数据增强
    FunnyBirds: 一个用于解释人工智能方法的基于部分的分析的合成视觉数据集
    Hbase工作原理
    Vue开发历程---音乐播放器
    Python Web开发框架:构建高效、可扩展的Web应用程序
  • 原文地址:https://blog.csdn.net/jgk666666/article/details/134355744