Leetcode695. 岛屿的最大面积

题目描述

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

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

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

示例 1:

1
2
3
4
5
6
7
8
[[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:

1
[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

这道题首先的思路就是暴力搜索，使用深度优先搜索。

首先需要写一个DFS的函数，作用是求解从某点(i,j)开始的连接在一起的岛屿的最大面积。首先需要指定递归出口：

1
2
3
if(i < 0 || i > grid.size() - 1 || j < 0 || j > grid[0].size() - 1){
        return 0;
}

这个的意思就是当递归的点跑出grid数组的范围时，直接返回；

然后就是递归求解的主要规律：

  • 当grid[i][j] == 0时，那么从这点开始的连接在一起的岛屿的最大面积肯定为0；
  • 当grid[i][j] == 1时，那么从这点开始的连接在一起的岛屿的最大面积就是从上下左右四个相连点递归得到的结果再加上1：
1
2
3
if(grid[i][j] == 1){
        return DFS(grid, visited, i - 1, j) + DFS(grid, visited, i + 1, j) + DFS(grid, visited, i, j - 1) + DFS(grid, visited, i, j + 1) + 1;
}

这样，我们可以通过 DFS 的函数求出任意一点开始的连接在一起的岛屿的最大面积。然后我们可以用两层循环，求出从每一点出发的连接在一起的岛屿的最大面积，取出最大值就是结果。

但是，这样的复杂度比较高，为了优化，我们可以用一个visited数组来标记已经递归过的点，避免无谓的计算，这样就可以保证每个点只递归一遍。

具体细节见参考代码。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int DFS(vector<vector<int>>& grid, vector<vector<int>>& visited, int i, int j){
    if(i < 0 || i > grid.size() - 1 || j < 0 || j > grid[0].size() - 1){
        return 0;
    }

    if(visited[i][j]){
        return 0;
    }

    visited[i][j] = 1;
    if(grid[i][j] == 1){
        return DFS(grid, visited, i - 1, j) + DFS(grid, visited, i + 1, j) + DFS(grid, visited, i, j - 1) + DFS(grid, visited, i, j + 1) + 1;
    }
    return 0;
}


int maxAreaOfIsland(vector<vector<int>>& grid){
    if(grid.empty()){
        return 0;
    }

    vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));
    int ans = 0;
    for(int i = 0; i < grid.size(); ++i){
        for(int j = 0; j < grid[0].size(); ++j){
            if(!visited[i][j]){
                ans = max(DFS(grid, visited, i, j), ans);
            }   
        }
    }

    return ans; 
}

复杂度分析

时间复杂度：O(R×C)O(R \times C)，其中 RR是给定网格中的行数，CC​是列数

空间复杂度：O(R×C)O(R \times C)，其中 RR是给定网格中的行数，CC是列数