给定一个由 0 和 1 组成的非空二维数组 grid ,用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿,则返回面积为 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
解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 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] is either 0 or 1
注意:本题与主站 695 题相同:
1、深度优先搜索;时间复杂度O(n^2),空间复杂度O(n)
func maxAreaOfIsland(grid [][]int) int {
maxArea := 0
for i := range grid {
for j := range grid[i] {
maxArea = max(maxArea, getArea(grid, i, j))
}
}
return maxArea
}
func getArea(grid [][]int, i, j int) int {
if grid[i][j] == 0 {
return 0
}
grid[i][j] = 0
area := 1
if i != 0 {
area = area + getArea(grid, i-1, j)
}
if j != 0 {
area = area + getArea(grid, i, j-1)
}
if i != len(grid)-1 {
area = area + getArea(grid, i+1, j)
}
if j != len(grid[0])-1 {
area = area + getArea(grid, i, j+1)
}
return area
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2、深度优先搜索;时间复杂度O(n^2),空间复杂度O(n)
func maxAreaOfIsland(grid [][]int) int {
res := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == 1 {
value := dfs(grid, i, j)
if value > res {
res = value
}
}
}
}
return res
}
func dfs(grid [][]int, i, j int) int {
if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) ||
grid[i][j] == 0 {
return 0
}
grid[i][j] = 0
res := 1
res = res + dfs(grid, i+1, j)
res = res + dfs(grid, i-1, j)
res = res + dfs(grid, i, j+1)
res = res + dfs(grid, i, j-1)
return res
}
Medium题目,题目同leetcode 695.岛屿的最大面积;类似的题目还有 leetcode 面试题16.19.水域大小
页面更新:2024-05-22
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号