岛屿的最大面积

剑指 Offer II 105. 岛屿的最大面积

给定一个由 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 题相同： https://leetcode.cn/problems/max-area-of-island/

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { } };

golang 解法, 执行用时: 8 ms, 内存消耗: 4.8 MB, 提交时间: 2022-11-20 16:59:35

func maxAreaOfIsland(grid [][]int) int {
	r, c := len(grid), len(grid[0])
	area, maxArea := 0, 0
	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			if grid[i][j] == 1 {
				area = getArea(grid, i, j)
				maxArea = max(maxArea, area)
			}
		}
	}
    return maxArea
}

func getArea(grid [][]int, i, j int) int {
	if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
		return 0
	}
	if grid[i][j] == 1 {
		grid[i][j] = 0
		return 1 + getArea(grid, i+1, j) + getArea(grid, i-1, j) + getArea(grid, i, j+1) + getArea(grid, i, j-1)
	}
	return 0
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

python3 解法, 执行用时: 68 ms, 内存消耗: 17.5 MB, 提交时间: 2022-11-20 16:58:42

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 以其中一块陆地为中心求岛屿面积
        def getArea(g: List[List[int]], i: int, j: int) -> int:
            if i < 0 or j < 0 or i >= len(g) or j >= len(grid[0]):
                return 0
            if g[i][j] == 1:
                g[i][j] = 0
                return 1 + getArea(g, i+1, j) + getArea(g, i-1, j) + getArea(g, i, j+1) + getArea(g, i, j-1)
            return 0

        r, c = len(grid), len(grid[0])
        area, maxArea = 0, 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 1:
                    area = getArea(grid, i, j)
                    maxArea = max(maxArea, area)
        return maxArea

上一题

下一题

详情