695. 岛屿的最大面积

https://leetcode-cn.com/problems/max-area-of-island/

解法一：dfs

类似于200.岛屿的个数。不同之处在于200题中不求面积，本题因为要求面积，需要考虑在递归函数中返回本层所得面积。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        maxArea = 0
        #遍历矩阵
        for i in range(m):
            for j in range(n):
                #每次dfs，更新最大面积
                maxArea = max(maxArea, self.dfs(grid, i, j))
        return maxArea
    
    def dfs(self, grid, i, j):
        #递归终点（越界，或为0）
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
            return 0
        #若为1
        grid[i][j] = 0  #置0    
        #递归访问上下左右，并累加面积
        area = 1 + self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1)
        return area

二、并查集

与200. 岛屿的个数不同，那题是求连通分量数，这题是求最大连通分量的size。

因为事先不知道1在哪些节点，因此没法用size数组确切的表示出所有1的连通分量大小，只能先预设size数组长度为m*n，初始所有节点连通分量大小都为1，然后求出所有连通分量的大小。

最后找最大连通分量，要避开0，因此遍历过程中不能使用200题中的优化技巧：访问1之后置0，毕竟后处理还要用到

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes, count):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = count
        # 树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
              # 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count

class Solution:
    def maxAreaOfIsland(self, grid) -> int:
        m,n = len(grid), len(grid[0])
        # 将二维坐标展平为一维
        def flat(x, y):
            return x * n + y
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    count += 1
        uf = UnionFind(m*n, count)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    # 看左右上下是否存在1
                    if j > 0 and grid[i][j - 1] == 1:
                        uf.union(flat(i, j), flat(i, j - 1))
                    if j < n - 1 and grid[i][j + 1] == 1:
                        uf.union(flat(i, j), flat(i, j + 1))
                    if i > 0 and grid[i - 1][j] == 1:
                        uf.union(flat(i, j), flat(i - 1, j))
                    if i < m - 1 and grid[i + 1][j] == 1:
                        uf.union(flat(i, j), flat(i + 1, j))

        res = 0
        for i in range(m):
            for j in range(n):
                if uf.size[flat(i,j)] > res and grid[i][j] != 0:
                    res = uf.size[flat(i, j)]
        return res