Medium

题目描述

给你一个大小为 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 ，因为岛屿只能包含水平或垂直方向的四个方向上相邻的土地。

示例 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

解题思路

解题思路

这是一道经典的图遍历问题，主要有以下几种解法：

方法一：深度优先搜索（DFS）【推荐】

我们需要遍历整个网格，当遇到值为1的陆地时，使用DFS来计算当前岛屿的面积。为了避免重复计算，我们在访问过的陆地上做标记（将1改为0或使用visited数组）。

具体步骤：

  1. 遍历网格中的每个位置
  2. 当发现陆地（值为1）时，启动DFS计算岛屿面积
  3. 在DFS过程中，将访问过的陆地标记为已访问，并累加面积
  4. 更新全局最大面积

方法二：广度优先搜索（BFS）

使用队列进行层次遍历，原理与DFS类似，但使用迭代方式实现。

方法三：并查集

通过并查集将相邻的陆地连通，最后统计各连通分量的大小。

DFS方法代码简洁，效率高，是最推荐的解法。时间复杂度为O(mn)，空间复杂度为O(mn)（递归栈深度）。

代码实现

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxArea = 0;
        int m = grid.size(), n = grid[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    maxArea = max(maxArea, dfs(grid, i, j));
                }
            }
        }
        
        return maxArea;
    }
    
private:
    int dfs(vector<vector<int>>& 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;  // 标记为已访问
        
        return 1 + dfs(grid, i-1, j) + dfs(grid, i+1, j) + 
               dfs(grid, i, j-1) + dfs(grid, i, j+1);
    }
};

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
                return 0
            
            grid[i][j] = 0  # 标记为已访问
            
            return 1 + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
        
        max_area = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j))
        
        return max_area

public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        int m = grid.Length, n = grid[0].Length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    maxArea = Math.Max(maxArea, DFS(grid, i, j));
                }
            }
        }
        
        return maxArea;
    }
    
    private int DFS(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].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);
    }
}

var maxAreaOfIsland = function(grid) {
    const dfs = (i, j) => {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型DFS解法BFS解法
时间复杂度O(m×n)O(m×n)
空间复杂度O(m×n)O(m×n)

其中 m 和 n 分别为网格的行数和列数。

  • 时间复杂度：每个位置最多访问一次
  • 空间复杂度：DFS的递归栈深度最坏情况下为O(m×n)，BFS的队列大小最坏情况下也为O(m×n)

相关题目