695. 岛屿的最大面积

image.png

递归解法

执行用时:3 ms, 在所有 Java 提交中击败了72.95% 的用户 内存消耗:38.8 MB, 在所有 Java 提交中击败了84.91% 的用户

  1. class Solution {
  2. // 存储是否遍历过
  3. private boolean[][] gridTemp;
  4. // 存储当前岛屿面积
  5. private int count;
  6. // 定义上下左右方向
  7. private int[][] dire = new int[][]{
  8. new int[]{0, 1},
  9. new int[]{0, -1},
  10. new int[]{1, 0},
  11. new int[]{-1, 0}
  12. };
  13. public int maxAreaOfIsland(int[][] grid) {
  14. int rowCount = grid.length;
  15. int colCount = grid[0].length;
  16. gridTemp = new boolean[rowCount][colCount];
  17. int max = 0;
  18. for (int i = 0; i < rowCount; i++) {
  19. for (int j = 0; j < colCount; j++) {
  20. if (!gridTemp[i][j]) {
  21. count = 0;
  22. calculateAreaRecursion(grid, i, j);
  23. max = Math.max(count, max);
  24. }
  25. }
  26. }
  27. return max;
  28. }
  29. public void calculateAreaRecursion(int[][] grid, int x, int y) {
  30. // 判断坐标是是否越界
  31. if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)) return;
  32. // 如果遍历过,返回
  33. if (gridTemp[x][y]) return;
  34. // 将当前坐标更新为已遍历
  35. gridTemp[x][y] = true;
  36. // 如果当前是岛屿,面积加一,
  37. if (grid[x][y] == 1) {
  38. count++;
  39. // 递归遍历上下左右节点
  40. for (int[] d : dire) {
  41. calculateAreaRecursion(grid, x + d[0], y + d[1]);
  42. }
  43. }
  44. }
  45. }