[LeetCode] 695. Max Area of Island

You are given an m x n binary matrix grid. 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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[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
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

岛屿的最大面积。

给你一个大小为 m x n 的二进制矩阵 grid 。

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

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道 flood fill 类型的题。我这里还是给出 DFS 和 BFS 两种做法。

无论是那种做法，search 一开始找的是值为 1 的坐标，这没有什么疑问。但是找到 1 之后，则需要把这个 1 当做一个岛的起点开始做 dfs。注意以下几点，同时也是 DFS 模板题都需要注意的

碰到边界就 return 0
把当前坐标的值 mark 成 0（或者一个极值，看情况而定，这是为了防止重复访问造成死循环）
四个方向递归调用 DFS 函数

这个题唯一多的一个步骤就是当找到第一个 1 的时候，需要把递归调用里面所有能找到的岛屿面积累加起来。

时间O(mn)

空间O(n)

Java实现

 1 class Solution {
 2     public int maxAreaOfIsland(int[][] grid) {
 3         int res = 0;
 4         int m = grid.length;
 5         int n = grid[0].length;
 6         for (int i = 0; i < m; i++) {
 7             for (int j = 0; j < n; j++) {
 8                 if (grid[i][j] == 1) {
 9                     res = Math.max(res, dfs(i, j, grid));
10                 }
11             }
12         }
13         return res;
14     }
15 
16     private int dfs(int i, int j, int[][] grid) {
17         if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
18             return 0;
19         }
20         grid[i][j] = 0;
21         int num = 1;
22         num += dfs(i + 1, j, grid);
23         num += dfs(i - 1, j, grid);
24         num += dfs(i, j + 1, grid);
25         num += dfs(i, j - 1, grid);
26         return num;
27     }
28 }

BFS 的实现也是类似，需要找到一个坐标值为 1 的坐标，然后放入 queue，依次看四个邻居坐标是否有更多的 1。当queue为空的时候，就知道当前的岛屿的面积是多少了，用这个面积去更新 res。

时间O(mn)

空间O(n)

Java实现

 1 class Solution {
 2     int[] dx = { 0, 0, 1, -1 };
 3     int[] dy = { 1, -1, 0, 0 };
 4 
 5     public int maxAreaOfIsland(int[][] grid) {
 6         int res = 0;
 7         int m = grid.length;
 8         int n = grid[0].length;
 9         for (int i = 0; i < m; i++) {
10             for (int j = 0; j < n; j++) {
11                 if (grid[i][j] == 1) {
12                     res = Math.max(res, helper(grid, i, j));
13                 }
14             }
15         }
16         return res;
17     }
18 
19     private int helper(int[][] grid, int i, int j) {
20         Queue<int[]> queue = new LinkedList<>();
21         queue.offer(new int[] { i, j });
22         grid[i][j] = 0;
23         int count = 1;
24         while (!queue.isEmpty()) {
25             int[] cur = queue.poll();
26             int x = cur[0];
27             int y = cur[1];
28             for (int index = 0; index < 4; index++) {
29                 int mx = x + dx[index];
30                 int my = y + dy[index];
31                 if (mx >= 0 && mx < grid.length && my >= 0 && my < grid[0].length && grid[mx][my] == 1) {
32                     queue.offer(new int[] { mx, my });
33                     grid[mx][my] = 0;
34                     count++;
35                 }
36             }
37         }
38         return count;
39     }
40 }

flood fill题型总结

LeetCode 题目总结