岛屿的最大面积

题意

给一个0/1的二维数组，问四连通的最大的1的块数

方法

广搜

分析

如果我们从一个为1的块开始，向它相邻的搜索

以此反复，搜索完所有相邻的为1的块

那么这个数量就是一个四连通的块数，其中最大值就是要求的答案

为了避免重复搜索，利用辅助数组记录一个块是否被搜索过即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxAreaIsland(vector<vector<int> >& grid) {
        vector<vector<bool>> vis(grid.size(),vector<bool>(grid[0].size(),false));
        int di[] = {0,1,0,-1};
        int dj[] = {1,0,-1,0};
        unsigned long area = 0;
        for(int i = 0;i<grid.size();i++){
            for(int j = 0;j<grid[0].size();j++){
                if(grid[i][j] == 0)continue; // 为1
                if(vis[i][j])continue; // 未访问过
                vis[i][j] = true; // 标记访问过 (选择的起始点)
                vector<pair<int,int> > ijs = {{i,j}}; // 广搜
                for(int o = 0;o<ijs.size();o++){ // 每次选择一个访问了但未扩展的点
                    auto [pi,pj] = ijs[o];
                    for(int k = 0;k<4;k++){ // 四个方向
                        auto ni = pi + di[k]; // 相邻坐标的i
                        auto nj = pj + dj[k]; // 相邻坐标的j
                        // 坐标不合法
                        if(ni < 0 || nj < 0 || ni >= grid.size() || nj >= grid[0].size() )continue;
                        // 非1 或者 访问过
                        if(grid[ni][nj] == 0 || vis[ni][nj] )continue;
                        vis[ni][nj] = true; // 标记访问
                        ijs.push_back({ni,nj}); // 扩展 加到搜索队尾
                    }
                }
                area = max(area,ijs.size()); // 最大块数记录
            }
        }
        return area;
    }
};

复杂度分析

空间复杂度: 用了额外的访问记录数组，空间复杂度为$O(nm)O(nm)$

时间复杂度: 对于每个块操作代价为常数，所以总时间复杂度为$O(nm)O(nm)$

并查集

分析

我们忽略它的二维数组的形态，只考虑它的连通关系

问题就变成了图论中求最大的并查集的大小

也就是初始化时，所有格子都是孤立的，后续处理每两个相邻的1会合并到一个并查集中

并查集中每个点记录它的直接的父节点，和并查集的大小，那么只有父节点是自己的节点的并查集大小才是有效值

样例

以样例数据为例

注意, 从数据结构上讲, 每个节点都有记录大小的字段, 但是只有并查集的根节点上的大小值才是真正表示当前并查集大小的

代码

class Solution {
public:
    // 坐标编码
    int enc(int i,int j,int sz){
        return i*sz+j;
    }
    // 获取并查集根
    int getfa(vector<pair<int,int> > & v2fc, int i){
        if(i == v2fc[i].first)return i;
        int r = getfa(v2fc, v2fc[i].first);
        v2fc[i] = v2fc[r];
        return r;
    }
    // 合并并查集，并返回合并后的并查集大小
    int merge(vector<pair<int,int> > & v2fc,int i,int j){
        // 获得分别的并查集根节点
        auto ri = getfa(v2fc,i);
        auto rj = getfa(v2fc,j);
        if(ri == rj)return v2fc[ri].second; // 本就是一个
        // 合并 rj为新的根
        v2fc[rj].second += v2fc[ri].second; // 更新并查集点数 
        v2fc[ri] = v2fc[rj];
        return v2fc[rj].second;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxAreaIsland(vector<vector<int> >& grid) {
        // 块 => 并查集父节点(father)，并查集大小(count)
        // 只有根是自己的 second才是准确的，根不是自己的节点的second是无效值
        vector<pair<int,int> > v2fc(grid.size()*grid[0].size());
        for(int i = 0;i<v2fc.size();i++){
            v2fc[i] = {i,1};// 初始化 fater = 自己,count = 1
        }
        int area = 0;
        // 只用处理每个块右侧和下侧的
        int di[] = {1,0};
        int dj[] = {0,1};
        for(int i = 0;i<grid.size();i++){
            for(int j = 0;j<grid[0].size();j++){
                if(grid[i][j] == 0)continue;
                area = max(area,1); // 没有两两相连的情况
                for(int k = 0;k < 2;k++){ // 两个方向（水平 和 垂直）
                    auto ni = i + di[k]; // 相邻坐标的i
                    auto nj = j + dj[k]; // 相邻坐标的j
                    // 坐标不合法
                    if(ni >= grid.size() || nj >= grid[0].size() )continue;
                    // 非1
                    if(grid[ni][nj] == 0)continue;
                    area = max(
                        area,
                        merge(
                            v2fc,
                            enc(i,j,grid[0].size()),
                            enc(ni,nj,grid[0].size())
                        )
                    );
                }
            }
        }
        return area;
    }
};

复杂度分析

空间复杂度: 主要消耗在并查集存储，空间复杂度为$O(nm)O(nm)$

时间复杂度: 对于并查集中每个节点的均摊操作代价为常数，所以总时间复杂度为$O(nm)O(nm)$