leetcode 695. Max Area of Island（岛屿的最大面积）-蒲公英云

leetcode 695. Max Area of Island（岛屿的最大面积）

https://leetcode.com/problems/max-area-of-island/

一、问题描述

给定一个二维数组，其所有元素均为1和0，分别代表陆地和水，数组边界四周都是水，求岛屿最大面积。

测试用例：

Input：
[[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]]
Output：
6
Input：
[[0,0,0,0,0,0,0,0]]
Output：
0

二、代码实现

二层循环遍历数组，如果当前元素是1，则计算该岛屿的面积后返回，然后与当前最大面积相比（如果比当前最大面积大，则更新最大面积），并且将岛屿的1置为0；如果当前元素是0，直接continue跳过当前元素。

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int maxArea = Integer.MIN_VALUE;
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return (maxArea == Integer.MIN_VALUE) ? 0 : maxArea;    //如果还是最小负数，说明没有岛屿，所以岛屿的最大面积为0
    }
    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        int area = 1;
        grid[i][j] = 0;
        area += dfs(grid, i-1, j);  //上
        area += dfs(grid, i+1, j);  //下
        area += dfs(grid, i, j-1);  //左
        area += dfs(grid, i, j+1);  //右
        return area;
    }
}