LeetCode-695. 岛屿的最大面积

题目描述

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

[[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:

[[0,0,0,0,0,0,0,0]] 对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。 链接：https://leetcode-cn.com/problems/max-area-of-island

我的AC代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var getArea = function(grid, i, j, count) {
    grid[i][j] = 0;
    if(j < grid[i].length - 1 && grid[i][j+1] == 1) {
        count++;
        count = getArea(grid, i, j+1, count);
    }
    if(i < grid.length -1 && grid[i+1][j] == 1) {
        count++;
        count = getArea(grid, i+1, j, count);
    }
    if(i > 0 && grid[i-1][j] == 1) {
        count++;
        count = getArea(grid, i-1, j, count);
    }
    if(j > 0 && grid[i][j-1] == 1) {
        count++;
        count = getArea(grid, i, j-1, count);
    }
    return count;
}
var maxAreaOfIsland = function(grid) {
    let res = 0;
    for(let i = 0; i < grid.length; i++) {
        for(let j = 0; j < grid[i].length; j++) {
            if(grid[i][j] == 1) {
                let count = getArea(grid, i, j, 1);
                res = Math.max(res, count);
            }
        }
    }
    return res;
};

解题思路

本题与https://github.com/hcc226/LeetcodeOJ/blob/master/200.%20%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F.md十分类似。 思路大致相同，不同之处是本题需要记录1的数量，同时记录当前最大的岛屿面积。