695.岛屿的最大面积
题目描述
给你一个大小为 m × n m \times n m×n 的二进制矩阵 g r i d grid grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
样例 #1
样例输入 #1
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]]
样例输出 #1
6
样例 #2
样例输入 #2
grid = [[0,0,0,0,0,0,0,0]]
样例输出 #2
0
提示
m = = g r i d . l e n g t h n = = g r i d [ i ] . l e n g t h 1 < = m , n < = 50 g r i d [ i ] [ j ] 为 0 或 1 。 m == grid.length\\ n == grid[i].length\\ 1 <= m, n <= 50\\ grid[i][j] 为 0 或 1。 m==grid.lengthn==grid[i].length1<=m,n<=50grid[i][j]为0或1。
做题思路
这道题的要点就在于如何计算每一个岛屿的面积。
因为已知上下左右相邻土地为算为同一岛屿。
假设能知道该土地属于哪一个岛屿，然后将同一岛屿的土地相加，就可以得到这块岛屿的面积。
那么恭喜你解锁了本题并查集的做法。
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
恰好适用于上面的归属问题思路。
首先我们将所有的土地各自归为一个岛屿。
再从上到下从左到右遍历全图。
如果碰到了土地，再看相邻的四个格子是不是土地，如果是那么就将这几个都合并在一个集合(岛屿)里面。
直到跑完全图，在算一次所有岛屿的最大面积即可。
但其实可以发现如果碰到了土地不需要看完相邻的四个格子，只需要看左边一个和上面一个。因为是从上到下从左到右遍历全图，下面和右边的格子随后会遍历到，并且也看左边和上面，可以容易证明不会拉下岛屿的每一寸土地。
时间复杂度分析
最多跑完四次全图
O
(
4
n
×
m
)
O(4n\times m)
O(4n×m)
实际上初始化和合并步骤可以合在一起
O
(
3
n
×
m
)
O(3n\times m)
O(3n×m)
伪代码
代码
class Solution {
public:
int pre[50][50];
int pa[2501];
int cnt[2501] = {0};
int find(int x){return pa[x] == x ? x : pa[x] =find(pa[x]);}
void unite(int x,int y){pa[find(x)] = find(y);}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int k = 0;
//init
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
pre[i][j] = ++k;
pa[k] = k;
}
}
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]){
if(i > 0 && grid[i-1][j])unite(pre[i][j],pre[i-1][j]);
if(j > 0 && grid[i][j-1])unite(pre[i][j],pre[i][j-1]);
}
}
}
int ans = 0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]){
cnt[find(pre[i][j])]++;
}
}
}
for(int i=1;i<=grid.size()*grid[0].size();i++)
ans = max(ans,cnt[i]);
return ans;
}
};
初始化和合并步骤合在一起后的代码
class Solution {
public:
int pre[50][50];
int pa[2501];
int cnt[2501] = {0};
int find(int x){return pa[x] == x ? x : pa[x] =find(pa[x]);}
void unite(int x,int y){pa[find(x)] = find(y);}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int k = 0;
//init
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
pre[i][j] = ++k;
pa[k] = k;
if(grid[i][j]){
if(i > 0 && grid[i-1][j])unite(pre[i][j],pre[i-1][j]);
if(j > 0 && grid[i][j-1])unite(pre[i][j],pre[i][j-1]);
}
}
}
int ans = 0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]){
cnt[find(pre[i][j])]++;
}
}
}
for(int i=1;i<=grid.size()*grid[0].size();i++)
ans = max(ans,cnt[i]);
return ans;
}
};