给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 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]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
这道题跟之前的那两道Number of Islands和Number of Distinct Islands是同一个类型的，只不过这次需要统计出每个岛的大小，再来更新结果res。
先用递归来做，遍历grid，当遇到为1的点，我们调用递归函数，在递归函数中，我们首先判断i和j是否越界，还有grid[i][j]是否为1，我们没有用visited数组，而是直接修改了grid数组，遍历过的标记为-1。如果合法，那么cnt自增1，并且更新结果res，然后对其周围四个相邻位置分别调用递归函数即可。
参见代码如下：
class Solution {
public:
vector dirs ;
int maxAreaOfIsland(vector& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 1) continue;
int cnt = 0;
helper(grid, i, j, cnt, res);
}
}
return res;
}
void helper(vector& grid, int i, int j, int& cnt, int& res) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) return;
res = max(res, ++cnt);
grid[i][j] *= -1;
for (auto dir : dirs) {
helper(grid, i + dir[0], j + dir[1], cnt, res);
}
}
};
下面是迭代的写法，BFS遍历，使用queue来辅助运算，思路没啥太大区别，都是套路，都是模版，往里套就行了。
参见代码如下：
class Solution {
public:
vector dirs ;
int maxAreaOfIsland(vector& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 1) continue;
int cnt = 0;
queue q };
grid[i][j] *= -1;
while (!q.empty()) {
auto t = q.front(); q.pop();
res = max(res, ++cnt);
for (auto dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= 0) continue;
grid[x][y] *= -1;
q.push({x, y});
}
}
}
}
return res;
}
};
类似题目：
Number of Distinct Islands
Island Perimeter
Number of Islands
