岛屿的最大面积(剑指Offer) -Java实现

Problem: LCR 105. 岛屿的最大面积

思路

本题中说的是一个网格的岛屿，获取其中的岛屿的最大面积，是典型的图论的问题，可以采用广度优先搜索算法和深度优先算法，本文采用广度优先搜索算法

解题方法

① 定义已经访问过的岛屿的二维布尔数组
② 两层循环遍历网格，即第一层(最外层)循环是网格的行，第二层(最内层)循环是网格的列
③ 遍历到每个网格节点时，判断该节点时岛屿(其值是1)，同时不是已经访问过的岛屿，则获取其岛屿的面积，并与最大的岛屿面积比较
④ 获取岛屿的面积的子函数 getArea(), 入参只要是 网格，是否已经访问过的二维数组，当前节点的横坐标，当前节点的纵坐标；返回值是整型的岛屿的面积
⑤ 获取岛屿面积的子函数中，定一个 岛屿节点Queue, Java语言中，就使用 LinkedList 实现就行，当前节点放入该队列，当前节点已访问，定义当前岛屿面积 area;
⑥ while循环岛屿节点队列，remove出当前岛屿节点，同时面积area增加1；for循环当前岛屿的前后左右四个节点，还是判断这四个节点的，纵横坐标是否在网格中，同时是否是岛屿，是否还没访问过，如果是的话，就放入到 岛屿节点队列中，这个节点被访问过

复杂度

• 时间复杂度: 两层循环，时间复杂度： O(n2)O(n^2)
  O(n2)

• 空间复杂度:空间复杂度： O(n)

Code

class Solution {public int maxAreaOfIsland(int[][] grid) {int maxArea = 0;int row = grid.length;int col = grid[0].length;// 岛屿是否访问过的二维布尔数组boolean[][] visited = new boolean[row][col];for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {// 节点是岛屿且没被访问过if (grid[i][j] == 1 && !visited[i][j]) {int area = getArea(grid, visited, i, j);maxArea = Math.max(area, maxArea);}}}return maxArea;}private int getArea(int[][] grid, boolean[][] visited, int i, int j) {// 岛屿节点队列Queue<int[]> queue = new LinkedList<>();int area = 0;queue.add(new int[]{i, j});visited[i][j] = true;// 岛屿的前后左右的四个方向int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 广度优先搜索while (!queue.isEmpty()) {// 当前节点int[] pos = queue.remove();area++;for (int[] dir : dirs) {int r = pos[0] + dir[0];int c = pos[1] + dir[1];if (r >= 0 && r < grid.length&& c >= 0 && c < grid[0].length&& grid[r][c] == 1 && !visited[r][c]) {queue.add(new int[]{r, c});visited[r][c] = true;}}}return area;}
}