Max Area of Island

最大岛屿面积

题目

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:

[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

解析重点

1.当遇到岛屿时我们要怎么计算岛屿面积呢？递归从四个方向计算面积，当遇到0时终止递归。注意，当递归到地图边界时也需要终止递归计算。
2.当一个岛屿我们从不同位置开始计算时，会出现重复计算的情况，我们可以把搜索过的位置置为0，后续就不会再计算了。
3.多个岛屿求最大面积，我们只需要保存最大值，然后每次碰到岛屿与之比较即可。

java代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int maxAera = maxAera(i, j, rows, cols, grid);//计算岛屿面积
                max = Math.max(maxAera, max);//计算最大岛屿
            }
        }
        return max;
    }

    private int maxAera(int i, int j, int rows, int cols, int[][] grid) {
        if (i < 0 || i >= rows || j < 0 || j >= cols||grid[i][j] == 0) return 0;//当当前点等于0或者到达边界时，直接返回0
        grid[i][j] = 0;//搜索过的点置为0
        return 1 + maxAera(i - 1, j, rows, cols, grid) + maxAera(i + 1, j, rows, cols, grid) + maxAera(i, j - 1, rows, cols, grid) + maxAera(i, j + 1, rows, cols, grid);//当前点是陆地时，从四个方向开始搜索
    }
}