leetcode
leetcode 2951 ~ 3000
岛屿的最大面积

岛屿的最大面积

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 40 ms, 内存: 16.7 MB


/*
 * 思路:
 * 使用Java Stream API实现同样的功能。 
 * 由于Stream不适用于带有副作用的操作, 我们仍然需要在循环中手动管理递归调用。
 */
import java.util.stream.*;

public class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int[] maxArea = {0};
        IntStream.range(0, grid.length).forEach(i ->
            IntStream.range(0, grid[i].length).forEach(j -> {
                if (grid[i][j] == 1) {
                    maxArea[0] = Math.max(maxArea[0], dfs(grid, i, j));
                }
            })
        );
        return maxArea[0];
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }
}

解释

方法:

该题解采用深度优先搜索(DFS)算法来解决岛屿的最大面积问题。从二维数组的每一个元素开始,如果当前元素是1(土地),则从该点出发使用DFS搜索所有连通的1,并在搜索过程中将遍历过的1设置为0以防重复计数。每次DFS会返回当前岛屿的面积,并与之前记录的最大面积进行比较,不断更新最大面积。这样,可以确保每个岛屿只被计算一次面积。

时间复杂度:

O(m*n)

空间复杂度:

O(m*n)

代码细节讲解

🦆
在DFS函数中,为什么在对当前土地进行标记为0后,才进行上下左右的递归搜索?这样做有什么特别的好处吗?
在DFS函数中,在进行上下左右的递归搜索之前将当前土地标记为0,是为了防止重复访问和计数。标记为0后,表示该土地已经被访问过,这样在后续的递归调用中,当遇到已标记为0的土地时,会直接返回0,不会再次计算其面积,从而避免重复计算。这种做法简化了逻辑,确保了每块土地只被计算一次,并且有效地防止了在递归过程中可能出现的无限循环。
🦆
题解中提到每个岛屿只被计算一次面积,这是如何保证的?具体是哪一部分代码实现了这一点?
在题解中,每个岛屿只被计算一次面积的保证是通过将访问过的1(土地)改为0(水)来实现的。这一操作在DFS函数中进行,具体在`grid[i][j] = 0`这一行代码中。这样,一旦某块土地被访问并参与到某个岛屿面积的计算中,它就被标记为0,使得后续的任何搜索不会再次将其计入另一个岛屿的面积,从而确保了每个岛屿的面积只被准确计算一次。
🦆
DFS递归调用栈在最坏情况下可能达到m*n的深度,这在什么样的grid配置下会发生?如何避免栈溢出?
DFS递归调用栈在最坏情况下可能达到m*n的深度,通常发生在整个网格都是陆地的情况下,例如当网格形状为一个很长的蛇形或完全填充的情况。在这种配置下,每个土地都连续递归访问,直到访问完所有的土地。为了避免栈溢出,可以考虑使用迭代的深度优先搜索(使用显式栈)或广度优先搜索(BFS)代替递归实现的DFS。BFS使用队列来实现,因此不会受到调用栈大小的限制,更适合处理大规模数据。

相关问题