岛屿的最大面积

695. 岛屿的最大面积

给你一个大小为 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 ，因为岛屿只能包含水平或垂直这四个方向上的 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] 为 0 或 1

相似题目

岛屿数量

岛屿的周长

原站题解

去查看

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

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

python3 解法, 执行用时: 96 ms, 内存消耗: 17.7 MB, 提交时间: 2022-08-26 11:47:48

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

golang 解法, 执行用时: 8 ms, 内存消耗: 4.9 MB, 提交时间: 2021-07-19 16:55:49

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
}

上一题

下一题

详情