517 字
3 分钟
LeetCode-695.岛屿的最大面积
图论
给你一个大小为
m x n的二进制矩阵grid。岛屿 是由一些相邻的
1(代表土地) 构成的组合，这里的「相邻」要求两个1必须在 水平或者竖直的四个方向上 相邻。你可以假设grid的四个边缘都被0（代表水）包围着。岛屿的面积是岛上值为
1的单元格的数目。计算并返回
grid中最大的岛屿面积。如果没有岛屿，则返回面积为0。
示例 1：
示例 2：
自己的解法(DFS)
我靠，怎么你和 200. 岛屿数量 的数组类型不一样的，害我看了好一会儿没看出来哪里有问题
思路：我认为是 200. 岛屿数量 + 543. 二叉树的直径
func maxAreaOfIsland(grid [][]int) int { if len(grid) == 0 { return 0 } maxcount := 0
var dfs func(r,c int) int dfs = func(r, c int) int { if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == 0 { return 0 }
grid[r][c] = 0
up := dfs(r-1, c) down := dfs(r+1, c) left := dfs(r, c-1) right := dfs(r, c+1)
if up + down + left + right + 1 > maxcount { maxcount = up + down + left + right + 1 }
return up + down + left + right + 1 }
for i := 0; i < len(grid); i++ { for j := 0; j < len(grid[0]); j++ { if grid[i][j] == 1 { dfs(i, j) } } }
return maxcount}稍微优化一下
func maxAreaOfIsland(grid [][]int) int { if len(grid) == 0 { return 0 } maxcount := 0
var dfs func(r, c int) int dfs = func(r, c int) int { if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == 0 { return 0 } grid[r][c] = 0 return 1 + dfs(r-1, c) + dfs(r+1, c) + dfs(r, c-1) + dfs(r, c+1) }
for i := 0; i < len(grid); i++ { for j := 0; j < len(grid[0]); j++ { if grid[i][j] == 1 { area := dfs(i, j) if area > maxcount { maxcount = area } } } } return maxcount} LeetCode-695.岛屿的最大面积
https://sheep44044.github.io/posts/算法/图论/leetcode-695岛屿的最大面积/