跳至主要內容

LeetCode 695、岛屿的最大面积

LeetCode 695、岛屿的最大面积

视频地址：LeetCode 695、岛屿的最大面积

一、题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

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

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

img
img

输入：

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、Java 代码

DFS解法

class Solution {
    private int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int x, y;
    private int area;

    public int maxAreaOfIsland(int[][] grid) {
        x = grid.length;      // 获得网格长
        y = grid[0].length;   // 获得网格宽
        int ans = 0;          // 初始化答案为0
        // 初始化数组checkList用于DFS遍历过程中的检查
        // false表示尚未访问，true表示已经访问
        boolean[][] checkList = new boolean[x][y];

        // 对整个grid二维数组进行双重循环遍历
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                // 若该点为陆地且还没有进行过搜寻
                if (grid[i][j] == 1 && !checkList[i][j]) {
                    // 在每一次DFS之前，先初始化面积为0
                    area = 0;
                    // 可以进行DFS
                    DFS(grid, i, j, checkList);
                    // 做完DFS，更新ans
                    ans = Math.max(ans, area);
                }
            }
        }
        return ans;
    }

    private void DFS(int[][] grid, int i, int j, boolean[][] checkList) {
        // 将该点标记为已经检查过
        checkList[i][j] = true;
        // 面积增大
        area++;
        // 遍历上下左右四个方向的邻点坐标
        for (int[] dir : DIRECTIONS) {
            int next_i = i + dir[0];
            int next_j = j + dir[1];
            // 若近邻点满足三个条件：
            // 1.没有越界    2. 近邻点尚未被检查过   3.近邻点也为陆地
            if (next_i >= 0 && next_i < x && next_j >= 0 && next_j < y &&
                    !checkList[next_i][next_j] && grid[next_i][next_j] == 1) {
                // 对近邻点(next_i, next_j)进行DFS搜索
                DFS(grid, next_i, next_j, checkList);
            }
        }
    }
}

BFS解法

class Solution {
    private int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        int xLen = grid.length;       // 获得网格长
        int yLen = grid[0].length;    // 获得网格宽
        int ans = 0;                  // 初始化陆地数目为0
        // 初始化和 grid 一样大小的二维数组 checkList 用于 BFS 遍历过程中的检查
        int[][] checkList = new int[xLen][yLen];
        // 双重遍历 grid 数组
        for (int i = 0; i < xLen; i++) {
            for (int j = 0; j < yLen; j++) {
                // 若该点为陆地且还没有进行过搜寻
                // 找到了一个 BFS 搜索的起始位置 (i, j)
                if (grid[i][j] == 1 && checkList[i][j] == 0) {
                    // 对于该片连通块，构建一个队列，初始化包含该点
                    Queue<int[]> q = new LinkedList<>();
                    q.offer(new int[]{i, j});
                    // 修改 checkList[i][j] 为 1，表示该点已经搜寻过
                    checkList[i][j] = 1;
                    // 进行 BFS 之前，初始化该连通块的面积为 0
                    int area = 0;
                    // 进行 BFS，退出循环的条件是队列为空
                    while (!q.isEmpty()) {
                        // 弹出栈队头的点 (x, y)，搜索该点上下左右的近邻点
                        int[] point = q.poll();
                        int x = point[0];
                        int y = point[1];
                        area++;
                        // 遍历 (x, y) 上下左右的四个方向的近邻点
                        for (int[] dir : DIRECTIONS) {
                            int xNext = x + dir[0];
                            int yNext = y + dir[1];
                            // 如果近邻点满足三个条件
                            if (xNext >= 0 && xNext < xLen && yNext >= 0 && yNext < yLen
                                    && checkList[xNext][yNext] == 0 && grid[xNext][yNext] == 1) {
                                // 对近邻点做两件事：
                                // 1. 入队       2. 标记为已检查过
                                q.offer(new int[]{xNext, yNext});
                                checkList[xNext][yNext] = 1;
                            }
                        }
                    }
                    // 更新答案
                    ans = Math.max(ans, area);
                }
            }
        }
        return ans;
    }
}

2、 C++ 代码

DFS解法

class Solution {
private:
    vector<vector<int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x, y;
    int area;

    void DFS(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& checkList) {
        // 将该点标记为已经检查过
        checkList[i][j] = true;
        // 面积增大
        area++;
        // 遍历上下左右四个方向的邻点坐标
        for (auto& dir : DIRECTIONS) {
            int next_i = i + dir[0];
            int next_j = j + dir[1];
            // 若近邻点满足三个条件：
            // 1.没有越界    2. 近邻点尚未被检查过   3.近邻点也为陆地
            if (next_i >= 0 && next_i < x && next_j >= 0 && next_j < y &&
                    !checkList[next_i][next_j] && grid[next_i][next_j] == 1) {
                // 对近邻点(next_i, next_j)进行DFS搜索
                DFS(grid, next_i, next_j, checkList);
            }
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        x = grid.size();         // 获得网格长
        y = grid[0].size();      // 获得网格宽
        int ans = 0;             // 初始化答案为0
        // 初始化数组checkList用于DFS遍历过程中的检查
        // false表示尚未访问，true表示已经访问
        vector<vector<bool>> checkList(x, vector<bool>(y, false));

        // 对整个grid二维数组进行双重循环遍历
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                // 若该点为陆地且还没有进行过搜寻
                if (grid[i][j] == 1 && !checkList[i][j]) {
                    // 在每一次DFS之前，先初始化面积为0
                    area = 0;
                    // 可以进行DFS
                    DFS(grid, i, j, checkList);
                    // 做完DFS，更新ans
                    ans = max(ans, area);
                }
            }
        }
        return ans;
    }
};

BFS解法

class Solution {
private:
    vector<vector<int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int xLen = grid.size();         // 获得网格长
        int yLen = grid[0].size();      // 获得网格宽
        int ans = 0;                    // 初始化陆地数目为0
        // 初始化和 grid 一样大小的二维数组 checkList 用于 BFS 遍历过程中的检查
        vector<vector<int>> checkList(xLen, vector<int>(yLen, 0));
        // 双重遍历 grid 数组
        for (int i = 0; i < xLen; i++) {
            for (int j = 0; j < yLen; j++) {
                // 若该点为陆地且还没有进行过搜寻
                // 找到了一个 BFS 搜索的起始位置 (i, j)
                if (grid[i][j] == 1 && checkList[i][j] == 0) {
                    // 对于该片连通块，构建一个队列，初始化包含该点
                    queue<pair<int, int>> q;
                    q.push(make_pair(i, j));
                    // 修改 checkList[i][j] 为 1，表示该点已经搜寻过
                    checkList[i][j] = 1;
                    // 进行 BFS 之前，初始化该连通块的面积为 0
                    int area = 0;
                    // 进行 BFS，退出循环的条件是队列为空
                    while (!q.empty()) {
                        // 弹出栈队头的点 (x, y)，搜索该点上下左右的近邻点
                        pair<int, int> point = q.front();
                        q.pop();
                        int x = point.first;
                        int y = point.second;
                        area++;
                        // 遍历 (x, y) 上下左右的四个方向的近邻点
                        for (auto& dir : DIRECTIONS) {
                            int xNext = x + dir[0];
                            int yNext = y + dir[1];
                            // 如果近邻点满足三个条件
                            if (xNext >= 0 && xNext < xLen && yNext >= 0 && yNext < yLen
                                    && checkList[xNext][yNext] == 0 && grid[xNext][yNext] == 1) {
                                // 对近邻点做两件事：
                                // 1. 入队       2. 标记为已检查过
                                q.push(make_pair(xNext, yNext));
                                checkList[xNext][yNext] = 1;
                            }
                        }
                    }
                    // 更新答案
                    ans = max(ans, area);
                }
            }
        }
        return ans;
    }
};

3、Python 代码

DFS解法

# 题目：LC695. 岛屿的最大面积
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问


# 初始化上下左右四个方向的数组
DERICTIONS = [(0,1), (1,0), (0,-1), (-1,0)]

class Solution:
    # 构建DFS函数
    def DFS(self, grid, i, j, checkList):
        # 将该点标记为已经检查过
        checkList[i][j] = True
        # 面积增大
        self.area += 1
        # 遍历上下左右四个方向的邻点坐标
        for dx, dy in DERICTIONS:
            next_i, next_j = i + dx, j + dy
            # 若近邻点满足三个条件：
            # 1.没有越界    2. 近邻点尚未被检查过   3.近邻点也为陆地
            if ((0 <= next_i < self.x and 0 <= next_j < self.y) and checkList[next_i][next_j] == False
                and grid[next_i][next_j] == 1):
                # 对近邻点(ni, nj)进行DFS搜索
                self.DFS(grid, next_i, next_j, checkList)

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.x = len(grid)      # 获得网格长
        self.y = len(grid[0])   # 获得网格宽
        ans = 0                 # 初始化答案为0
        # 初始化数组checkList用于DFS遍历过程中的检查
        # 0表示尚未访问，1表示已经访问
        checkList = [[False] * self.y for _ in range(self.x)]

        # 对整个grid二维数组进行双重循环遍历
        for i in range(self.x):
            for j in range(self.y):
                # 若该点为陆地且还没有进行过搜寻
                if grid[i][j] == 1 and checkList[i][j] == False:
                    # 在每一次DFS之前，先初始化面积为0
                    self.area = 0
                    # 可以进行DFS
                    self.DFS(grid, i, j, checkList)
                    # 做完DFS，更新ans
                    ans = max(ans, self.area)
        return ans

BFS解法

# 题目：LC695. 岛屿的最大面积
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问


# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        x_len, y_len = len(grid), len(grid[0])       # 获得网格长宽
        ans = 0                                      # 初始化陆地数目为0
        # 初始化和grid一样大小的二维数组checkList用于DFS遍历过程中的检查
        checkList = [[0] * y_len for _ in range(x_len)]
        # 双重遍历grid数组
        for i in range(x_len):
            for j in range(y_len):
                # 若该点为陆地且还没有进行过搜寻
                # 找到了一个BFS搜索的起始位置(i,j)
                if grid[i][j] == 1 and checkList[i][j] == 0:
                    # 对于该片连通块，构建一个队列，初始化包含该点
                    q = deque()
                    q.append((i,j))
                    # 修改checkList[i][j]为1，表示该点已经搜寻过
                    checkList[i][j] = 1
                    # 进行BFS之前，初始化该连通块的面积为0
                    area = 0
                    # 进行BFS，退出循环的条件是队列为空
                    while len(q) > 0:
                        # 弹出栈队头的点(x,y) 搜寻该点上下左右的近邻点
                        x, y = q.popleft()
                        area += 1
                        # 遍历(x,y)上下左右的四个方向的近邻点
                        for dx, dy in DIRECTIONS:
                            x_next, y_next = x+dx, y+dy
                            # 如果近邻点满足三个条件
                            if (0 <= x_next < x_len and 0 <= y_next < y_len and checkList[x_next][y_next] == 0 
                                    and grid[x_next][y_next] == 1):
                                    # 对近邻点做两件事：
                                    # 1. 入队       2. 标记为已检查过
                                    q.append((x_next, y_next))
                                    checkList[x_next][y_next] = 1
                    # 更新答案
                    ans = max(ans, area)
        return ans
本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法