岛屿的最大面积
难度:
标签:
题目描述
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递归调用栈在最坏情况下可能达到m*n的深度,这在什么样的grid配置下会发生?如何避免栈溢出?
▷