leetcode Depth-First Search

leetcode 695题

Posted by franki on February 3, 2021

leetcode 695题 岛屿的最大面积

给定一个包含了一些 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。

思路

深度优先遍历

代码

var maxAreaOfIsland = function (grid) {
  const x = grid.length;
  const y = grid[0].length;
  let max = 0;
  for (let i = 0; i < x; i++) {
    for (let j = 0; j < y; j++) {
      if (grid[i][j] === 1) {
        max = Math.max(max, countArea(grid, i, j, x, y));
      }
    }
  }

  return max;
};

function countArea(grid, i, j, x, y) {
  if (i < 0 || i >= x || j < 0 || j >= y || grid[i][j] === 0) return 0;
  let cnt = 1;
  grid[i][j] = 0;
  cnt += countArea(grid, i + 1, j, x, y);
  cnt += countArea(grid, i - 1, j, x, y);
  cnt += countArea(grid, i, j + 1, x, y);
  cnt += countArea(grid, i, j - 1, x, y);
  return cnt;
}

复杂度分析

  • 时间复杂度: O(N*M)
  • 空间复杂度: O(N*M)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS