695. 岛屿的最大面积
给你一个大小为
m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的
1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为
1 的单元格的数目。计算并返回
grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。示例 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]] 输出：6 解释：答案不应该是11 ，因为岛屿只能包含水平或垂直这四个方向上的1 。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j]为0或1
通过次数151,198提交次数226,293
法1 DFS
思路
DFS,有点像 37. 解数独 ，遍历每一个入口
又有点像 79. 单词搜索 记住走过的路径
题解
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: self.res = 0 self.used = [[False]* len(grid[0]) for _ in grid] for i in range(0, len(grid)): for j in range(0, len(grid[0])): if grid[i][j] == 1 and not self.used[i][j]: self.res = max(self.res, self.dfs(grid, i, j)) return self.res def dfs(self, grid, row, col): if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]): return 0 if grid[row][col] == 0 or self.used[row][col]: return 0 res = 1 self.used[row][col] = True res += self.dfs(grid, row+1, col) res += self.dfs(grid, row-1, col) res += self.dfs(grid, row, col+1) res += self.dfs(grid, row, col-1) return res
法2 DFS 迭代
思路
深度优先搜索每一个合适入口的岛屿面积，只不过是采用栈迭代dfs
题解
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: res = 0 used = [[False]*len(grid[0]) for _ in grid] def dfs(grid, r, c): res = 0 used[r][c] = True dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]] stack = [] stack.append([r,c]) while stack: cur = stack.pop() res += 1 for dir_ in dirs: x = cur[0] + dir_[0] y = cur[1] + dir_[1] if len(grid) > x >= 0 and len(grid[0]) > y >= 0 and not used[x][y] and grid[x][y] == 1: stack.append([x, y]) used[x][y] = True return res for i in range(0, len(grid)): for j in range(0 ,len(grid[0])): if grid[i][j] == 1 and not used[i][j]: res = max(res, dfs(grid, i, j)) return res
法3 BFS
思路
采用BFS来搜索每个岛屿的面积。
题解
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: res = 0 used = [[False]*len(grid[0]) for _ in grid] def bfs(grid, r, c): res = 0 used[r][c] = True dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]] queue = [] queue.append([r,c]) while queue: cur = queue.pop(0) res += 1 for dir_ in dirs: x = cur[0] + dir_[0] y = cur[1] + dir_[1] if len(grid) > x >= 0 and len(grid[0]) > y >= 0 and not used[x][y] and grid[x][y] == 1: queue.append([x, y]) used[x][y] = True return res for i in range(0, len(grid)): for j in range(0 ,len(grid[0])): if grid[i][j] == 1 and not used[i][j]: res = max(res, bfs(grid, i, j)) return res
法 4 并查集
思路
采用并查集来统计每个岛屿的面积！
题解
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: res = 0 flag = False # 用来标记 有没有使用并查集，因为不使用并查集，uf.size 也都是1 m, n = len(grid), len(grid[0]) dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]] uf = Unionfind(m*n) for i in range(0, m): for j in range(0, n): if grid[i][j] == 1: flag = True # 对每一个 1 的四围都进行遍历，再遇到1 就直接union # 不要怕多次重复union, 因为如果本身就是在同一个集合中，在union一次也只是查找两次而已，不会改变树结构 for dir_ in dirs: x, y = i + dir_[0], j + dir_[1] if m > x >= 0 and n > y >= 0 and grid[x][y] == 1: uf.union(i*n + j, x*n + y) return max(uf.size) if flag else 0 # 模板！！！ 背下来直接用 class Unionfind: def __init__(self, n): self.size = [1] * n self.parents = [i for i in range(n)] def find(self, x): if self.parents[x] != x: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: if self.size[root_x] >= self.size[root_y]: self.parents[root_y] = root_x self.size[root_x] += self.size[root_y] else: self.parents[root_x] = root_y self.size[root_y] += self.size[root_x]