LeetCode 695. 岛屿的最大面积

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 695. 岛屿的最大面积

思路分析

感染

参考代码

func maxAreaOfIsland(grid [][]int) int {
	if len(grid) == 0 {
		return 0
	}

	row := len(grid)
	col := len(grid[0])
	maxArea := 0

	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		// 边界条件
		if r < 0 || r >= row || c < 0 || c >= col || grid[r][c] == 0 {
			return 0
		}
		// 标记为已访问
		grid[r][c] = 0
		// 计算当前岛屿的面积
		area := 1
		area += dfs(r+1, c)
		area += dfs(r-1, c)
		area += dfs(r, c+1)
		area += dfs(r, c-1)
		return area
	}

	for r := 0; r < row; r++ {
		for c := 0; c < col; c++ {
			if grid[r][c] == 1 {
				area := dfs(r, c) // 进行 DFS，计算面积
				if area > maxArea {
					maxArea = area // 更新最大面积
				}
			}
		}
	}
	
	return maxArea
}

func maxAreaOfIsland(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	maxArea := 0

	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				area := dfs(grid, i, j)
				maxArea = max(maxArea, area)
			}
		}
	}

	return maxArea
}

func dfs(grid [][]int, row, col int) int {
	if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] != 1 {
		return 0
	}

	// 将当前位置标记为已访问
	grid[row][col] = 0

	// 递归搜索相邻的岛屿
	area := 1
	area += dfs(grid, row+1, col)
	area += dfs(grid, row-1, col)
	area += dfs(grid, row, col+1)
	area += dfs(grid, row, col-1)

	return area
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

🍏 点击查看 Java 题解

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j);
                    res = Math.max(res, area);
                }
            }
        }
        return res;
    }

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/66529937