来源：LeetCode
难度：中等
描述：
给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0)
示例1：
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例2：
对于上面这个给定的矩阵, 返回 0。
分析：题目将1代表土地，0代表水，让我们返回上下左右连在一起的最大的土地，就是让我们找到二维数组中数量最多的连在一起的1，此处可以采用深度和广度的方法来解
题外话：二维数组、有向图、邻接链表等用来表示图的数据结构，咱基本都可采用深搜或者广搜的方法来解，需要注意的是要对搜索过的位置进行标识，防止重复搜索
解题
方法一：深度优先遍历解题
思路：采用深度优先遍历遍历数组每个节点，当找到等于1的节点时，开始计数，同时找该节点的上下左右四个方向的节点，对于非0节点计数累加，需要注意对遍历过的节点进行标识，可以采用map或者二维数组标记，由于该题不要求咱们不能动原数组，咱直接将遍历过的节点置为0，遇到为0的节点直接跳过即可
代码：
1public int maxAreaOfIsland(int[][] grid) {
2 if (grid == null || grid.length == 0) {
3 return 0;
4 }
5 int res = 0;
6 for (int i = 0; i < grid.length; i++) {
7 for (int j = 0; j < grid[i].length; j++) {
8 //只针对为1的节点进行搜索
9 if (grid[i][j] == 1) {
10 //每块相连的1的个数与 res进行比较，只保留最大的相连的个数
11 res = Math.max(res, dfs(grid, i, j));
12 }
13 }
14 }
15 return res;
16}
17private int dfs(int[][] grid, int i, int j) {
18 //越界和非1直接跳过
19 if (i < 0 || j < 0 || i == grid.length
20 || j == grid[i].length || grid[i][j] == 0) {
21 return 0;
22 }
23 //遍历过的1直接置为0
24 grid[i][j] = 0;
25 int res = 1;
26
27 //上
28 res += dfs(grid, i, j - 1);
29 //下
30 res += dfs(grid, i, j + 1);
31 // 左
32 res += dfs(grid, i - 1, j);
33 //右
34 res += dfs(grid, i + 1, j);
35
36 return res;
37}题外话：咱只要记住 深搜用栈，广搜用队列，这两类的题就好解了，而上面的解法用的递归系统栈替换自己构造栈实现，下面咱用队列来解一下
方法二：广度优先遍历解题
思路：遍历二维数组每个元素，对于非0的节点将其横纵坐标分别入队，同时将其上下左右都入队，对遍历过的节点进行标识，直接置0即可，直到遍历完所有元素
代码：
1public int maxAreaOfIsland3(int[][] grid) {
2 int ans = 0;
3 for (int i = 0; i != grid.length; ++i) {
4 for (int j = 0; j != grid[0].length; ++j) {
5 if (grid[i][j] == 0) {
6 continue;
7 }
8 int cur = 0;
9 //存放非0节点横坐标
10 Queue<Integer> queueI = new LinkedBlockingQueue<>();
11 //存放非0节点纵坐标
12 Queue<Integer> queueJ = new LinkedBlockingQueue<Integer>();
13 queueI.offer(i);
14 queueJ.offer(j);
15 while (!queueI.isEmpty()) {
16 int cur_i = queueI.poll(), cur_j = queueJ.poll();
17 //越界 非1 跳过
18 if (cur_i < 0 || cur_j < 0 || cur_i == grid.length
19 || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
20 continue;
21 }
22 ++cur;
23 //遍历过的节点置0
24 grid[cur_i][cur_j] = 0;
25
26 //用循环来描述上下左右
27 int[] di = {0, 0, 1, -1};
28 int[] dj = {1, -1, 0, 0};
29 for (int index = 0; index != 4; ++index) {
30 //i + 0, j + 1 下
31 //i + 0, j - 1 上
32 //i + 1, j + 0 右
33 //i - 1, j + 0 左
34 int next_i = cur_i + di[index], next_j = cur_j + dj[index];
35 //将上下左右的横纵坐标入队
36 queueI.offer(next_i);
37 queueJ.offer(next_j);
38 }
39 }
40 //取最大
41 ans = Math.max(ans, cur);
42 }
43 }
44 return ans;
45}
以上仅是个人思路解法
转载请注明：XAMPP中文组官网 » 数组篇6_岛屿的最大面积[难度：中等]