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

曾经终败给现在 2022-12-03 09:55 128阅读 0赞

[https://leetcode.com/problems/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;
        }
    }

[https_leetcode.com_problems_max-area-of-island]: https://leetcode.com/problems/max-area-of-island/