京东2024年年终奖大幅提升，采销岗平均薪酬将达23薪。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

随着2025年春节的日益临近，各大互联网公司的春节假期安排和年终奖发放成为了广大员工和网友们热议的话题。

12月23日，京东发布了2024年年终奖发放计划，这是京东要实现从16薪迈向20薪的第一年。实现17薪的部门内年度绩效A+的员工将实现20薪，采销岗平均23薪，差不多相当于干一年发两年的工资，这年终奖确实挺诱人。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第695题：岛屿的最大面积。

问题描述

来源：LeetCode第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 。

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 50

• grid[i][j] 为 0 或 1

问题分析

这题让计算岛屿的最大面积，岛屿的面积是通过上下左右相连接的 1 的个数。这题有多种解决方式，BFS，DFS和并查集都可以解决，之前我们讲过这道题，当时使用的是 BFS- ，这里我们使用 DFS 再来解这道题。

关于DFS的知识我们在 中也讲过，不过这里遍历的不是图，而是矩阵，实际上原理都是一样的。

在矩阵中每个位置最多只有上下左右四个和它相连，我们 遍历矩阵的每一个位置，如果当前位置是 1 ，表示它是岛屿，然后开始计算岛屿的面积。 就是以当前位置为起始点沿着它的上下左右四个方向查找，如果遇到 1 ，说明它们是同一个岛屿，累加面积，然后再把它变成 0 ，表示该位置已经计算过了，防止重复计算，最后只需要返回最大面积即可。

这里还要注意遍历的时候不能越界，只能访问矩阵内的位置。

JAVA：

public int maxAreaOfIsland(int[][] grid) {     int m = grid.length, n = grid[0].length;// 矩阵的宽和高     int ans = 0;// 记录最大面积     for (int i = 0; i < m; i++)         for (int j = 0; j < n; j++)             if (grid[i][j] == 1) // 当前位置如果是 1 ，开始计算                 ans = Math.max(ans, dfs(grid, i, j, m, n));     return ans; } public int dfs(int[][] grid, int i, int j, int m, int n) {     // 边界条件的判断，不能越界     if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {         // 当前位置如果是1，为了防止重复计算就把他置为0，然后再从他的上下左右四个方向开始查找         grid[i][j] = 0;         return 1 + dfs(grid, i + 1, j, m, n) + dfs(grid, i - 1, j, m, n)                 + dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n);     }     return 0; }

C++：

public:     int maxAreaOfIsland(vector

 > &grid) {         int m = grid.size(), n = grid[0].size();// 矩阵的宽和高         int ans = 0;// 记录最大面积         for (int i = 0; i < m; i++)             for (int j = 0; j < n; j++)                 if (grid[i][j] == 1) // 当前位置如果是 1 ，开始计算                     ans = max(ans, dfs(grid, i, j, m, n));         return ans;     }     int dfs(vector

 > &grid, int i, int j, int m, int n) {         // 边界条件的判断，不能越界         if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {             // 当前位置如果是1，为了防止重复计算就把他置为0，然后再从他的上下左右四个方向开始查找             grid[i][j] = 0;             return 1 + dfs(grid, i + 1, j, m, n) + dfs(grid, i - 1, j, m, n)                    + dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n);         }         return 0;     }

Python：

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:     def dfs(i, j):         # 边界条件的判断，不能越界         if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:             # 当前位置如果是1，为了防止重复计算就把他置为0，然后再从他的上下左右四个方向开始查找             grid[i][j] = 0             return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j - 1) + dfs(i, j + 1)         return 0     m, n = len(grid), len(grid[0])  # 矩阵的宽和高     ans = 0  # 记录最大面积     for i in range(m):         for j in range(n):             if grid[i][j] == 1:  # 当前位置如果是 1 ，开始计算                 ans = max(ans, dfs(i, j))     return ans

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。