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; } }