深度优先搜索、栈

题目

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0）

示例：

Input:
[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
Output: 6
最大的岛屿面积为 6，位于最右侧。

题解

方法一：深度优先搜索

  • 确定一块土地时，从四个方向考虑，为了避免每块土地多次计算，每次访问后将其赋值为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxAreaOfIsland(self,grid):# grid :List[list[int]]
        maxArea=0
        for i,l in enumerate(grid):
            for j,n in enumerate(l):
                maxArea=max(self.dfs(grid,i,j),maxArea)
        return maxArea
    def dfs(self,grid,cur_i,cur_j):
        if cur_i<0 or cur_j<0 or cur_i==len(grid) or cur_j==len(grid[0]) or grid[cur_i][cur_j]!=1:
            return 0
        grid[cur_i][cur_j]=0
        ans=1
        for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:
            next_i,next_j = cur_i+di,cur_j+dj
            ans +=self.dfs(grid,next_i,next_j)
        return ans
1
2
3
4
5
grid=[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
a = Solution()
a.maxAreaOfIsland(grid)
6

复杂度分析

时间复杂度：O(R×C)。其中 R 是给定网格中的行数，C是列数。我们访问每个网格最多一次。

空间复杂度：O(R×C)。递归的深度最大可能是整个网格的大小，因此最大可能使用 O(R×C) 的栈空间。

方法二：深度优先搜索 + 栈

这种方法本质与方法一相同，唯一的区别是

  • 方法一通过函数的调用来表示接下来想要遍历哪些土地，让下一层函数来访问这些土地。而方法二把接下来想要遍历的土地放在栈里，然后在取出这些土地的时候访问它们。
  • 访问每一片土地时，我们将对围绕它四个方向进行探索，找到还未访问的土地，加入到栈 stack 中；
  • 另外，只要栈 stack 不为空，就说明我们还有土地待访问，那么就从栈中取出一个元素并访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxAreaOfIsland(self,grid):# grid:List[List[int]]
        maxArea=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                curArea=0
                stack = [(i,j)]
                while stack:
                    cur_i,cur_j=stack.pop()
                    if cur_i<0 or cur_j<0 or cur_i==len(grid) or cur_j==len(grid[0]) or grid[cur_i][cur_j]!=1:
                        continue
                    curArea+=1
                    grid[cur_i][cur_j]=0
                    for di,dj in [[1,0],[-1,0],[0,1],[0,-1]]:
                        next_i,next_j=cur_i+di,cur_j+dj
                        stack.append((next_i,next_j))
                maxArea=max(curArea,maxArea)
        return maxArea
1
2
3
4
5
grid=[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
a = Solution()
a.maxAreaOfIsland(grid)
6

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/03/10/LeetCode-H-%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95-695.%20%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF/