摘要：找到给定的二维数组中最大的岛屿面积。思路给定一个由和组成的二维数组，其中代表岛屿土地，要求找出二维数组中最大的岛屿面积，没有则返回。样例如样例所示，二维数组的最大岛屿面积为，下面来讲解深度优先搜索的做法。
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
[[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:
[[0,0,0,0,0,0,0,0]]对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
(DFS) O ( n ∗ m ) O(n*m) O(n∗m)
给定一个由0和1组成的二维数组grid，其中1代表岛屿土地，要求找出二维数组中最大的岛屿面积，没有则返回0。
样例：
如样例所示，二维数组grid的最大岛屿面积为4，下面来讲解深度优先搜索的做法。
我们定义这样一种搜索顺序，即先搜索岛屿上的某块土地，然后以4个方向向四周探索与之相连的每一块土地，搜索过程中维护一个area变量，用来记录搜索过的土地总数。为了避免重复搜索，在这个过程中需要将已经搜索过的土地置为0，最后我们返回最大的area即可。
搜索函数设计：
int dfs(int x, int y)x，y是当前搜索到的二维数组grid的横纵坐标。
实现细节：
grid以及二维数组的行数n和列数m都定义为全局变量可以减少搜索函数dfs的参数数量。具体过程如下：
res = 0，遍历grid数组。grid数组元素grid[i][j] == 1，也就是说为土地的话，就以当前土地(i,j)为起点继续向四周搜索联通的土地。area中。res = max(res,area),不断更新答案。时间复杂度分析： O ( n ∗ m ) O(n*m) O(n∗m)， n n n是二维数组的行数， m m m是二维数组的列数，每个位置只被搜索一次。
class Solution {public: int n, m; vector<vector<int>>g; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //偏移数组 int dfs(int x, int y) //搜索函数 { int area = 1; g[x][y] = 0; //已经搜索过，标记为0 for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; //当前土地未出界也未被搜索过，继续下一层搜索 if(a >=0 && a < n && b >=0 && b < m && g[a][b]) area += dfs(a, b); } return area; //返回连通土地总数 } int maxAreaOfIsland(vector<vector<int>>& grid) { g = grid; int res = 0; n = grid.size(), m = grid[0].size(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(g[i][j]) res = max(res,dfs(i,j)); return res; }};class Solution { private int n, m; private int[][] g; private int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};//偏移数组 public int dfs(int x, int y) //搜索函数 { int area = 1; g[x][y] = 0; //已经搜索过，标记为0 for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; //当前土地未出界也未被搜索过，继续下一层搜索 if(a >=0 && a < n && b >= 0 && b < m && g[a][b] != 0) area += dfs(a, b); } return area; //返回连通土地总数 } public int maxAreaOfIsland(int[][] grid) { g = grid; int res = 0; n = grid.length; m = grid[0].length; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(g[i][j] != 0) res = Math.max(res,dfs(i,j)); return res; }}原题链接： 695. 岛屿的最大面积
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119113.html
摘要：示例输入输出示例输入输出示例输入输出示例输入输出思路贪心给定一组非负数，重新排列使其组成一个最大的整数。具体过程如下自定义排序规则函数，将数组按照自定义排序规则重新排序。时间复杂度分析排序的时间复杂度为。 ...
摘要：给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。状态表示表示偷窃号到号房间所能获得的最高金额。下标均从开始打家劫舍我们已经知道了房间单排排列的状态转移方程，接下来思考房间环状排列的做法。 ...
摘要：返回注意答案并不是因为陆地相连要求必须是在上下左右四个方向。返回应为想法我们还是要遍历数组中的每一个元素。如果数组元素值为，则我们以这个值为起点进行深度优先搜索。 题目详情 Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-di...
摘要：题目链接题目分析给定一组坐标，返回能组成面积最大的三角形面积。思路只能套循环了。利用三边求面积公式得面积。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D77 812. Largest Triangle Area 题目链接 812. Largest Triangle Area 题目分析 给定一组坐标，返回能组成面积最大的三角形面积。 思路 只能套for循环了。利用三边求面积公式得面...
摘要：思路从题目解析可以得知，每一面每一行或每一列取最大值相加即可。传进来的是一个二维数组。固定时二维数组的第个元素代表时，的值轴的间隔为第个元素代表时，的值。计算二维数组每一个元素中，相同位置的值的最高值即可。 883. Projection Area of 3D Shapes 题目链接 883. Projection Area of 3D Shapes 题目分析 这个题目要求计算一个三维...
阅读 523·2021-11-25 09:44
阅读 2600·2021-11-24 09:39
阅读 2250·2021-11-22 15:29
阅读 3490·2021-11-15 11:37
阅读 3342·2021-09-24 10:36
阅读 2456·2021-09-04 16:41
阅读 927·2021-09-03 10:28
阅读 1749·2019-08-30 15:55
