跳至主要內容

0695. 岛屿的最大面积

ITCharge大约 3 分钟

0695. 岛屿的最大面积open in new window

  • 标签:深度优先搜索、广度优先搜索、并查集、数组、矩阵
  • 难度:中等

题目链接

题目大意

描述:给定一个只包含 0011 元素的二维数组,11 代表岛屿,00 代表水。一座岛的面积就是上下左右相邻的 11 所组成的连通块的数目。

要求:计算出最大的岛屿面积。

说明

  • m==grid.lengthm == grid.length
  • n==grid[i].lengthn == grid[i].length
  • 1m,n501 \le m, n \le 50
  • grid[i][j]grid[i][j]0011

示例

  • 示例 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

解题思路

思路 1:深度优先搜索

  1. 遍历二维数组的每一个元素,对于每个值为 11 的元素:
    1. 将该位置上的值置为 00(防止二次重复计算)。
    2. 递归搜索该位置上下左右四个位置,并统计搜到值为 11 的元素个数。
    3. 返回值为 11 的元素个数(即为该岛的面积)。
  2. 维护并更新最大的岛面积。
  3. 返回最大的到面积。

思路 1:代码

class Solution:
    def dfs(self, grid, i, j):
        n = len(grid)
        m = len(grid[0])
        if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == 0:
            return 0
        ans = 1
        grid[i][j] = 0
        ans += self.dfs(grid, i + 1, j)
        ans += self.dfs(grid, i, j + 1)
        ans += self.dfs(grid, i - 1, j)
        ans += self.dfs(grid, i, j - 1)
        return ans

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    ans = max(ans, self.dfs(grid, i, j))
        return ans

思路 1:复杂度分析

  • 时间复杂度O(n×m)O(n \times m),其中 mmnn 分别为行数和列数。
  • 空间复杂度O(n×m)O(n \times m)

思路 2:广度优先搜索

  1. 使用 ansans 记录最大岛屿面积。
  2. 遍历二维数组的每一个元素,对于每个值为 11 的元素:
    1. 将该元素置为 00。并使用队列 queuequeue 存储该节点位置。使用 tempanstemp\underline{}ans 记录当前岛屿面积。
    2. 然后从队列 queuequeue 中取出第一个节点位置 (i,j)(i, j)。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为 00(避免重复搜索)。并将其加入到队列中。并累加当前岛屿面积,即 temp_ans += 1
    3. 不断重复上一步骤,直到队列 queuequeue 为空。
    4. 更新当前最大岛屿面积,即 ans = max(ans, temp_ans)
  3. ansans 作为答案返回。

思路 2:代码

import collections

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        rows, cols = len(grid), len(grid[0])
        ans = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    grid[i][j] = 0
                    temp_ans = 1
                    q = collections.deque([(i, j)])
                    while q:
                        i, j = q.popleft()
                        for direct in directs:
                            new_i = i + direct[0]
                            new_j = j + direct[1]
                            if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols or grid[new_i][new_j] == 0:
                                continue
                            grid[new_i][new_j] = 0
                            q.append((new_i, new_j))
                            temp_ans += 1

                    ans = max(ans, temp_ans)
        return ans

思路 2:复杂度分析

  • 时间复杂度O(n×m)O(n \times m),其中 mmnn 分别为行数和列数。
  • 空间复杂度O(n×m)O(n \times m)