azl397985856 commented 3 years ago

695. 岛屿的最大面积

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/max-area-of-island/

前置知识

暂无

题目描述

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

yanglr commented 3 years ago

思路:

题意: 0表示水, 1表示陆地。

需要找到上下左右四连通的最多个相邻1的数量。

第一感觉: Floodfill(洪水填充)模板题, 实现用bfs/dfs均可。

如何确定面积最大的岛屿?

找出所有岛屿面积, 取出其中最大值。

方法: flood fill算法(dfs版)

flood fill的具体做法:

步骤1.如果一个格子是陆地(数字1), 就把它上下左右4个方向中相邻的1全弄成0, 然后统计其数量.
步骤2.对每一个格子使用步骤1的做法, 每次分别记录值都为1的连通块的数量, 并更新最大值后返回。

实现flood fill算法, 这里我们选用dfs来实现。

代码

实现语言: C++

class Solution {
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int m, n;
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {       
        m = grid.size();
        n = grid[0].size();
        int res = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                    res = max(res, dfs(grid, i, j));
            }
        }
        return res;
    }
    int dfs(vector<vector<int>>& grid, int x, int y) /* G[i][j] == 1时才调用dfs */
    {
        int res = 1; // 把当前格子加进来
        grid[x][y] = 0; /* 加完之后就将用水(0)代替之前的陆地(1), 目的是避免重复访问。用这种方法就不需要使用visited数组记录状态了 */
        for (int i = 0; i < 4; i++)
        {
            auto a = x + dx[i];
            auto b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n) // 确保没越界
            {
                if (grid[a][b] == 1)
                    res += dfs(grid, a, b); // 把连通块数累加一下
            }          
        }
        return res;
    }
};

复杂度分析

时间复杂度: O(m * n), m 和 n 分别是二维数组的行数和列数
空间复杂度: O(1)

ZETAVI commented 3 years ago

思路

深度优先探索矩阵中每个数值为一的点,以寻找他们附近是否有"土地"

语言

java

代码

public class Solution {
    static final int[][] direction = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        return traver(grid);
    }

    private int traver(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    ans = Math.max(ans, DFS(i, j, grid));
                }
            }
        }
        return ans;
    }

    private int DFS(int i, int j, int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0) return 0;
        int count = 1;
        grid[i][j] = 0;
        for (int[] direct : direction) {
            count += DFS(i + direct[0], j + direct[1], grid);
        }
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
                {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}
        };
        System.out.println(solution.maxAreaOfIsland(grid));
    }
}

复杂度分析

时间复杂度:$O(R \times C)$ 其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。
空间复杂度:$O(R \times C)$ 递归的深度最大可能是整个网格的大小，因此最大可能使用 $O(R \times C)$的栈空间。

ninghuang456 commented 3 years ago

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int max = 0;
        for (int i = 0; i < row; i ++){
            for (int j = 0; j < col; j ++){
                if (grid[i][j] == 1){
                    int area = getArea(grid, i , j);
                    max = Math.max(area, max);
                }
            }
        }
        return max;
    }

    public int getArea(int[][] grid, int i, int j){
        if (!inArea(grid, i, j)){
            return 0;
        }
        if (grid[i][j] != 1){
            return 0;
        }
        grid[i][j] = 2;
        int sum = 1 + getArea(grid, i - 1, j) + getArea(grid, i, j - 1) + getArea(grid, i + 1, j) + getArea(grid, i, j + 1);   
        return sum; 
    }

    public boolean inArea(int[][] grid, int i, int j){
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}
//DFS 
// Time O(m*n)
// Space O(1)

zhangzz2015 commented 3 years ago

思路

标准的图的遍历问题，每一个岛屿其实对应一个生成树，只要找到一个为1点作为起始点，进行dfs遍历，统计相连的1的个数，为了避免loop。对于遍历过的1，改成2,。主函数遍历所有grid节点。时间复杂度为O(n^2)，空间复杂度为O(树的最大深度），最差情况也是O(n^2)。

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {

        int ret =0; 
        for(int i=0; i< grid.size(); i++)
        {
            for(int j=0; j< grid[i].size(); j++)
            {
                int count =0; 
               if(grid[i][j]==1)
               {
                   dfs(grid, i, j, count); 
                   if(count > ret)
                       ret = count; 
               }
            }
        }
        return ret; 

    }
    vector<int> direction={-1, 0 , 1, 0, -1};
    void dfs(vector<vector<int>>&grid, int row, int col, int & count)
    {
        if(row<0|| row>=grid.size() || col <0 || col>=grid[0].size())
            return; 

        if(grid[row][col]==2||grid[row][col]==0) // visit. 
            return; 

        count++; 
        grid[row][col] =2;  //change 1 to 2. visit. 

        for(int i=0; i< direction.size()-1; i++)
        {
            dfs(grid, row + direction[i], col + direction[i+1], count); 
        }

    }
};

kidexp commented 3 years ago

thoughts

可以用BFS, DFS, 和union find 这里写了前两种

code

from typing import List
from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        """
        BFS
        """
        visited_set = set()
        max_area = 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] and (i, j) not in visited_set:
                    queue = deque([(i, j)])
                    visited_set.add((i, j))
                    area = 0
                    while queue:
                        c_i, c_j = queue.pop()
                        area += 1
                        for delta_i, delta_j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            new_i, new_j = c_i + delta_i, c_j + delta_j
                            if (
                                0 <= new_i < m
                                and 0 <= new_j < n
                                and grid[new_i][new_j]
                                and (new_i, new_j) not in visited_set
                            ):
                                visited_set.add((new_i, new_j))
                                queue.appendleft((new_i, new_j))
                    max_area = max(max_area, area)
        return max_area

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        """
        DFS
        """
        visited_set = set()
        max_area = 0
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            visited_set.add((i, j))
            area = 0
            for delta_i, delta_j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_i, new_j = i + delta_i, j + delta_j
                if (
                    0 <= new_i < m
                    and 0 <= new_j < n
                    and grid[new_i][new_j]
                    and (new_i, new_j) not in visited_set
                ):
                    area += dfs(new_i, new_j)
            return 1 + area

        for i in range(m):
            for j in range(n):
                if grid[i][j] and (i, j) not in visited_set:
                    max_area = max(max_area, dfs(i, j))
        return max_area

complexity

m, n = len(grid), len(grid[0])

Time O(mn)

Space O(mn)

cicihou commented 3 years ago


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        '''
        跟 200 的思路一样，只是需要注意如何在 dfs 中进行适当的返回
        :param grid:
        :return:

        time: O(R*C)
        space: O(R*C)
        R 是行，C 是列
        '''
        def dfs(i, j):
            count = 0
            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:
                grid[i][j] = 2
                count += 1
                return count + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)
            else:
                return 0

        m, n = len(grid), len(grid[0])
        max_count = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    count = dfs(i, j)
                    max_count = max(count, max_count)
        return max_count

leo173701 commented 3 years ago


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: 
            return 0
        row = len(grid)
        col = len(grid[0])  
        res = 0
        def BFS(grid, i, j, row, col):
            curCount = 1
            q = [(i,j)]
            while q:
                cur = q.pop(0)
                for (x,y) in [(cur[0]+1,cur[1]),(cur[0]-1,cur[1]),(cur[0],cur[1]+1),(cur[0],cur[1]-1)]:
                    if 0<=x<row and 0<=y<col and grid[x][y]==1:
                        q.append((x,y))
                        curCount +=1
                        grid[x][y]=0
            return curCount
        for i in range(row):
            for j in range(col):
                if grid[i][j]==1:
                    grid[i][j]=0
                    res = max(res,BFS(grid,i,j,row,col))
        return res```

pophy commented 3 years ago

思路

DFS

Java Code

class Solution {
private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int maxAreaOfIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length, res = 0;        
    for (int i = 0;i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {                    
                res = Math.max(res,dfs(grid, i, j));
            }
        }
    }
    return res;
}

private int dfs(int[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j]== 0 {
        return 0;
    }
    grid[i][j] = 0;
    int res = 1;
    for (int[] d : directions) {
        res += dfs(grid, i + d[0], j + d[1]);
    }        
    return res;
}    
}

时间&空间

时间 O(m*n)
空间 O(1)

yachtcoder commented 3 years ago

DFS, Union Find O(MN), O(MN)

class UF:
    def __init__(self):
        self.parents = {}
        self.sizes = defaultdict(lambda: 1)
    def merge(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        self.parents[px] = py
        self.sizes[py] += self.sizes[px]
    def find(self, x):
        self.parents.setdefault(x, x)
        ox = x 
        while self.parents[x] != x:
            x = self.parents[x]
        self.parents[ox] = x
        return x

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        def adj(x, y):
            dirs = [[0,1], [1, 0], [0,-1], [-1,0]]
            for d in dirs:
                nx, ny = x + d[0], y + d[1]
                if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] == 1:
                    yield nx, ny
        def byuf():
            uf = UF()
            ret = 0
            for x in range(M):
                for y in range(N):
                    if grid[x][y] == 1:
                        for nx, ny in adj(x, y):
                            uf.merge((x,y), (nx,ny))
                        ret = max(uf.sizes[uf.find((x,y))], ret)
            return ret
        return byuf()

        def dfs(x, y):
            ret = 1
            for nx, ny in adj(x, y):
                grid[nx][ny] = 2
                ret += dfs(nx, ny)
            return ret

        ret = 0
        for x in range(M):
            for y in range(N):
                if grid[x][y] == 1:
                    grid[x][y] = 2
                    ret = max(ret, dfs(x, y))
        return ret

thinkfurther commented 3 years ago

思路

逐个格子往外搜索，并把本格标记为搜索过

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.m = len(grid)
        if self.m == 0:
            return 0
        self.n = len(grid[0])
        ans = 0
        for i in range(self.m):
            for j in range(self.n):
                ans = max(ans, self.bfs(i,j))
        return ans

    def bfs(self, i, j):
        q = collections.deque()
        q.append((i,j))
        current = 0
        while q:
            i, j = q.popleft()
            if i < 0 or i >= self.m or j < 0 or j >= self.n:
                continue
            if self.grid[i][j] == 0:
                continue
            current += 1
            self.grid[i][j] = 0
            q.append((i + 1,j))
            q.append((i - 1, j))
            q.append((i, j - 1))
            q.append((i, j + 1))
        return current

复杂度

时间复杂度：O(N*M)

空间复杂度：O(N*M)

xinhaoyi commented 3 years ago

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

思路一

DFS即可

对数组进行遍历，当值不为0时对其进行dfs操作，使用search数组记录是否遍历过。

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        //创建search数组
        boolean[][] search = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; ++i) {
            //填充数组
            Arrays.fill(search[i], true);
        }
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                //如果值大于0，且没被遍历过，就dfs它
                if (grid[i][j] > 0 && search[i][j]) {
                    int num = dfs(grid, i, j, search);
                    max = max > num ? max : num;
                }
            }
        }
        return max;

    }

    //dfs
    int dfs(int[][] grid, int i, int j, boolean[][] search) {
        search[i][j] = false;
        int n = grid.length - 1;
        int m = grid[0].length - 1;
        int num = 1;
        if (i > 0) {
            if (grid[i - 1][j] > 0 && search[i - 1][j]) {
                num += dfs(grid, i - 1, j, search);
            }
        }
        if (j > 0) {
            if (grid[i][j - 1] > 0 && search[i][j - 1]) {
                num += dfs(grid, i, j - 1, search);
            }
        }
        if (i < n) {
            if (grid[i + 1][j] > 0 && search[i + 1][j]) {
                num += dfs(grid, i + 1, j, search);
            }
        }
        if (j < m) {
            if (grid[i][j + 1] > 0 && search[i][j + 1]) {
                num += dfs(grid, i, j + 1, search);
            }
        }
        return num;
    }
}

Gjts commented 3 years ago

语言 CSharp

时间复杂度：O(m * n)
空间复杂度：O(m * n)

思路：使用DFS 深度优先搜索这道题有点递归路径那意思

操作：

网格问题一般都是双for循环查一下每一个网格是不是有等于1的
然后判断它上下左右是不是等于1
它是不是在符合条件的网格内做一些边界检查
找到了就换一个状态避免死循环

注意：可以把方法拆分一下做到单一原则

code

public int MaxAreaOfIsland(int[][] grid) {
        int row = grid.Length;
        int col = grid[0].Length;
        int ans = 0;
        for(int r = 0; r < row; r++)
        {
            for(int c = 0; c < col; c++)
            {
                if(grid[r][c] == 1) //找到了一个
                {
                    int sum = DFS(grid, r, c); //上下左右加起来的值
                    ans = Math.Max(ans, sum); 
                }
            }
        }
        return ans;
    }
    int DFS(int[][] grid, int r, int c)
    {
        if(!InArea(grid, r, c)) // 超出边界
        {
            return 0;
        }
        if(grid[r][c] != 1) //还真不在岛上 
        {
            return 0;
        }
        //找到了 把状态换了 不然会发生死循环 旋转跳跃我闭着眼
        grid[r][c] = 2; 
        //找到了 返回1 + 上 + 下 + 左 + 右
        return 1 + DFS(grid, r - 1, c) + DFS(grid, r + 1, c) + DFS(grid, r, c - 1) + DFS(grid, r, c + 1);
    }
    bool InArea(int[][] grid, int r, int c)
    {
        return 0 <= r && r < grid.Length && 0 <= c && c < grid[0].Length; //对网格的边界进行判断 到底是不是在棋盘内
    }

james20141606 commented 3 years ago

Day 50: 695. Max Area of Island (search, DFS, BFS)

Problem Link
- 695. Max Area of Island
Ideas
- use DFS, for every position, if it is not out of bounds, use dfs to search its neighboring. for each non zero position we add 1. the trick is for the visited position we set to 0.
Complexity: hash table and bucket
- Time: O(RC) #row and column
- Space: O(RC)
Code

class Solution:
    def dfs(self, grid, cur_i, cur_j) -> int:
        if cur_i < 0 or cur_j < 0 or cur_i >= len(grid) or cur_j >= len(grid[0]) or grid[cur_i][cur_j] != 1:
            return 0
        grid[cur_i][cur_j] = 0  #this is the trick
        ans = 1  #for non-zero position the area is 1
        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ans += self.dfs(grid, cur_i + di, cur_j + dj)
        return ans

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        #loop through all the positions
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                ans = max(self.dfs(grid, i, j), ans)
        return ans

other resources:
- https://leetcode-cn.com/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/
- https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

zhy3213 commented 3 years ago

思路

区域生长，把生长过的区域标0，可以减少无用的遍历。在原有数组外圈pad一圈0，可以简化生长时的代码，保证数组不越界。

代码

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def grow(grid,x,y):
            res=1
            grid[y][x]=0
            if grid[y-1][x]==1:
                res+=grow(grid,x,y-1)
            if grid[y+1][x]==1:
                res+=grow(grid,x,y+1)
            if grid[y][x-1]==1:
                res+=grow(grid,x-1,y)
            if grid[y][x+1]==1:
                res+=grow(grid,x+1,y)
            return res
        pad=[[0]*len(grid[0])]
        grid.extend(pad)
        pad.extend(grid)
        grid=pad
        list(map(lambda x: x.append(0),grid))
        list(map(lambda x: x.insert(0,0),grid))
        res, tmp=0, 0
        for y,row in enumerate(grid):
            for x,i in enumerate(row):
                if i==1:
                    tmp=grow(grid,x,y)
                    if tmp>res:
                        res=tmp
        return res

yingliucreates commented 3 years ago

link:

https://leetcode.com/problems/max-area-of-island/

代码 Javascript

function maxAreaOfIsland(grid) {
  let max = 0;
  let rows = grid.length;
  let cols = grid[0].length;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        max = Math.max(max, helper(i, j, grid));
      }
    }
  }
  return max;
};

function helper(i, j, grid) {
  let count = 0;
  if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) {
    return 0;
  }
  grid[i][j] = 0;
  count++
  count += helper(i+1, j, grid);
  count += helper(i-1, j, grid);
  count += helper(i, j+1, grid);
  count += helper(i, j-1, grid);
  return count;
}

复杂度分析

time: O(mn)?

nonevsnull commented 3 years ago

思路

拿到题的直觉解法
- 标准的graph dfs/bfs模版题；
- 难点不在思路，而是在写法上；
- 这题做过很多遍，每次写法都不同，但都很丑很差很啰嗦；这种问题就是写完了没思考没整理模版造成的。
- 第一次dfs：其实没必要directions，也没必要visited，返回值size在递归参与运算也有点危险；总的来说就是只为这个题；
- 第二次bfs：也很啰嗦；
- 第三次dfs：递归更清晰(递归返回值：1即当前cell面积+分支的面积和，结束条件越界或非1)，visited就是在线改；这种写法写多几次，就会有印象什么时候合适。

AC

代码

//第一次dfs
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int[][] visited = new int[grid.length][grid[0].length];
        int[][] directions = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
        int max = 0;
        for(int row = 0;row < grid.length;row++){
            for(int col = 0;col < grid[0].length;col++){
                if(grid[row][col] != 0 && visited[row][col] != 1){
                    max = Math.max(max, dfs(grid, new int[]{row, col}, 0, visited, directions));
                }
            }
        }
        return max;
    }

    public int dfs(int[][] grid, int[] cur, int size, int[][] visited, int[][] directions){

        size++;
        visited[cur[0]][cur[1]] = 1;
        for(int[] direction: directions){
            int nextRow = cur[0] + direction[0];
            int nextCol = cur[1] + direction[1];
            if(nextRow >= 0 && nextRow < grid.length && nextCol >= 0 && nextCol < grid[0].length && visited[nextRow][nextCol] == 0 && grid[nextRow][nextCol] != 0){
                visited[nextRow][nextCol] = 1;
                size = dfs(grid, new int[]{nextRow, nextCol}, size, visited, directions);
            } 
        }

        return size;

    }
}
//第二次bfs
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for(int row = 0;row < grid.length;row++){
            for(int col = 0;col < grid[0].length;col++){
                if(grid[row][col] == 1){
                    res = Math.max(res, bfs(grid, row, col));
                }
            }
        }

        return res;
    }

    public int bfs(int[][] grid, int row, int col){
        int res = 0;
        int[][] directions = {{1,0},{0,1},{-1,0},{0,-1}};
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[]{row, col});
        res++;
        grid[row][col] = 0;
        while(!q.isEmpty()){
            int size = q.size();

            for(int i = 0;i < size;i++){
                int[] cur = q.poll();
                for(int[] direction: directions){
                    int nr = cur[0] + direction[0];
                    int nc = cur[1] + direction[1];
                    if(nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1){
                        q.add(new int[]{nr, nc});
                        res++;
                        grid[nr][nc] = 0;
                    }
                }

            }
        }
        return res;
    }
}
//第三次
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for(int row = 0;row < grid.length;row++){
            for(int col = 0;col < grid[0].length;col++){
                if(grid[row][col] == 1){
                    max = Math.max(max, dfs(grid, new int[]{row, col}));
                }
            }
        }

        return max;
    }

    public int dfs(int[][] grid, int[] cell){
        if(cell[0] < 0 || cell[0] >= grid.length || cell[1] < 0 || cell[1] >= grid[0].length || grid[cell[0]][cell[1]] == 0){
            return 0;
        }

        grid[cell[0]][cell[1]] = 0;
        return 1 + dfs(grid, new int[]{cell[0] + 1, cell[1]}) + dfs(grid, new int[]{cell[0] - 1, cell[1]}) + dfs(grid, new int[]{cell[0], cell[1] + 1}) + dfs(grid, new int[]{cell[0], cell[1] - 1});
    }
}

复杂度

N = row * col time: O(N)，遍历每个cell space: O(N)，最坏情况满格的话每个cell都drill down形成了N层stack

q815101630 commented 3 years ago

经典dfs

非常经典的dfs， dfs 的basecase 是当当前cell 越界或者等于0，那么意味着我们不能根据当前cell向四个方向蔓延，所以返回0，而如果可以，设置当前cell为0，就返回 1 + dfs(i+1,j)+dfs(i-1,j)+dfs(i, j+1)+dfs(i, j-1)。就count 当前岛屿的大小。外层再来个double for loop 遍历即可

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        def dfs(i, j):
            if not (0<= i <len(grid) and 0<= j <len(grid[0])):
                return 0
            if not grid[i][j]:
                return 0
            grid[i][j] = 0
            return 1 + dfs(i+1,j)+dfs(i-1,j)+dfs(i, j+1)+dfs(i, j-1)

        maxi = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]:
                    maxi = max(maxi, dfs(i,j))

        return maxi

时间: O(mn). DFS只需要遍历所有cell一次空间: O(mn): 空间最大可能为最大岛屿的面积

florenzliu commented 3 years ago

Explanation

dfs
change island (1) to -1 after visiting

Python

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        row, col = len(grid), len(grid[0])

        def dfs(m, n, grid):
            nonlocal count
            if m < row and n < col and m >= 0 and n >= 0 and grid[m][n] == 1:
                count += 1
                grid[m][n] = -1
                dfs(m-1, n, grid)
                dfs(m+1, n, grid)
                dfs(m, n-1, grid)
                dfs(m, n+1, grid)
            return

        maxArea = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    count = 0
                    dfs(i, j, grid)
                    maxArea = max(count, maxArea)
        return maxArea

Complexity:

Time Complexity: O(mn) where m and n are the row and column of the grid, respectively
Space Complexity: O(mn)

itsjacob commented 3 years ago

Intuition

one pass dfs/bfs with a helper array visited

Implementation

class Solution
{
public:
  int maxAreaOfIsland(vector<vector<int>> &grid)
  {
    // use a visited array of the same size as grid
    int m = grid.size();
    int n = grid[0].size();
    std::vector<std::vector<bool>> visited(m);
    for (int jj = 0; jj < m; jj++) {
      visited[jj] = std::vector<bool>(n, false);
    }

    int res{ 0 };
    for (int jj = 0; jj < m; jj++) {
      for (int ii = 0; ii < n; ii++) {
        if (visited[jj][ii] || grid[jj][ii] == 0) continue;
        dfs(grid, jj, ii, visited, res);
      }
    }
    return res;
  }

private:
  void dfs(std::vector<std::vector<int>> &grid, int jj, int ii, std::vector<std::vector<bool>> &visited, int &res)
  {
    int count{ 0 };
    dfs_helper(grid, jj, ii, visited, count);
    res = std::max(res, count);
  }

  void dfs_helper(std::vector<std::vector<int>> &grid, int jj, int ii, std::vector<std::vector<bool>> &visited,
                  int &count)
  {
    if (visited[jj][ii]) return;
    visited[jj][ii] = true;
    count++;
    if (jj < grid.size() - 1 && grid[jj + 1][ii] != 0) {
      dfs_helper(grid, jj + 1, ii, visited, count);
    }
    if (jj > 0 && grid[jj - 1][ii] != 0) {
      dfs_helper(grid, jj - 1, ii, visited, count);
    }
    if (ii < grid[0].size() - 1 && grid[jj][ii + 1] != 0) {
      dfs_helper(grid, jj, ii + 1, visited, count);
    }
    if (ii > 0 && grid[jj][ii - 1] != 0) {
      dfs_helper(grid, jj, ii - 1, visited, count);
    }
    return;
  }
};

Complexity

Time complexity: O(m*n)
Space complexity: O(m*n)

erik7777777 commented 3 years ago

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    res = Math.max(res, calculate(grid, i, j));
                }
            }
        }
        return res;
    }

    private int calculate(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        int res = 1;
        res += calculate(grid, i + 1, j) + calculate(grid, i - 1, j) + calculate(grid, i, j + 1) + calculate(grid, i, j - 1);
        return res;
    }
}

Complexity Time O(m n) Space O(m n)

ZacheryCao commented 3 years ago

Idea:

DFS. For each land, search its neightbors and record its coordinate. We also can directly change the value to 0 to minimize the space, but it will change the grid. Here, I use a set to record the coordinates.

Code:

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n < 1:
            return 0
        m = len(grid[0])
        if m < 1:
            return 0
        seen = set()
        def dfs(grid, i, j, seen):
            if i< 0 or i > n- 1 or j < 0 or j > m - 1 or (i, j) in seen or grid[i][j] == 0:
                return 0
            seen.add((i,j))
            return 1 + dfs(grid, i+1, j, seen) + dfs(grid, i, j+1, seen) + dfs(grid, i-1, j, seen) + dfs(grid, i, j-1, seen)
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    ans = max(ans, dfs(grid, i, j, seen))
        return ans

Complexity:

Time: O(N). N is the size of grid. Because we use recursion, which will search each cell in the grid. Space: O(N). For the seen set(), it's size is O(N). The recurison's call stack also will use O(N).

JiangyanLiNEU commented 3 years ago

Idea

DFS : mark all the island that we visited

Runtime: O(row*column), space: O(1)

Python Code

class Solution(object):
def maxAreaOfIsland(self, grid):
    directions = [[0,1],[1,0],[-1,0],[0,-1]]
    def dfs(row, column):
        now = 0
        for di, dj in directions:
            newI, newJ = row+di, column+dj
            if 0 <= newI < len(grid) and 0 <= newJ < len(grid[0]):
                if grid[newI][newJ] == 1:
                    grid[newI][newJ] = '#'
                    now += 1+dfs(newI, newJ)
        return now

    result = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 1:
                area = 1
                grid[i][j] = '#'
                area += dfs(i,j)
                result = max(result, area)
    return result

mixtureve commented 3 years ago

思路

dfs

代码

语言支持：Java

Java Code:


class Solution {
    private int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int max = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    max = Math.max(max, dfs(i, j, grid, visited));
                }
            }
        }
        return max;
    }

    private int dfs(int x, int y, int[][] grid, boolean[][] visited) {
        visited[x][y] = true;

        // 当前的点 + 1
        int area = 1;

        for (int[] dir: directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];

            if (isValid(grid.length, grid[0].length, newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1) {
                area += dfs(newX, newY, grid, visited);        
            }
        }
        return area;
    }

    private boolean isValid (int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

复杂度分析

时间复杂度：$O(m * n)$ we visited every point once
空间复杂度：$O(m * n)$

laofuWF commented 3 years ago

# dfs
# time: O(m*n)
# space: O(m*n)

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        res = 0

        rows = len(grid)
        cols = len(grid[0])
        visited = [[0 for i in range(cols)] for j in range(rows)]

        def dfs(i, j, visited):
            dx = [0, 1, 0, -1]
            dy = [1, 0, -1, 0]
            visited[i][j] = 1
            count = 1

            for k in range(4):
                new_i = i + dx[k]
                new_j = j + dy[k]

                if new_i <= rows - 1 and new_i >= 0 and new_j <= cols - 1 and new_j >= 0 and visited[new_i][new_j] == 0 and grid[new_i][new_j] == 1:

                    count += dfs(new_i, new_j, visited)

            return count

        for i in range(rows):
            for j in range(cols):
                if visited[i][j] == 0 and grid[i][j] == 1:

                    res = max(dfs(i, j, visited), res)

        return res

heyqz commented 3 years ago

DFS

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or r == m or c < 0 or c == n or grid[r][c] == 0: 
                return 0
            grid[r][c] = 0  # Mark as visited
            return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c-1) + dfs(r, c+1)

        ans = 0
        for r in range(m):
            for c in range(n):
                ans = max(ans, dfs(r, c))
        return ans

time complexity: O(mn) space complexity: O(mn)

jsu-arch commented 3 years ago

思路

BFS


from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        num_rows = len(grid)
        num_cols = len(grid[0])
        visited = [[0] * num_cols for _ in range(num_rows)]

        max_island_size = 0
        deltas = [(1,0), (-1,0), (0,1), (0,-1)]
        for i in range(num_rows):
            for j in range(num_cols):
                if grid[i][j] == 1 and visited[i][j] == 0:
                    queue = deque([(i,j)])
                    visited[i][j] = 1
                    island_size = 0
                    while len(queue) > 0:
                        r, c = queue.popleft()
                        island_size += 1
                        for dr, dc in deltas:
                            if r + dr >= 0 and r + dr < num_rows \
                            and c + dc >= 0 and c + dc < num_cols \
                            and grid[r+dr][c+dc] == 1 and visited[r+dr][c+dc] == 0:
                                queue.append((r+dr, c+dc))
                                visited[r+dr][c+dc] = 1
                    max_island_size = max(max_island_size, island_size)

        return max_island_size

Complexity

Time Complexity: O（mn) Space Complexity: O(mn)

Bochengwan commented 3 years ago

思路

BFS

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        seen = set()
        ans = 0
        row= len(grid)
        col = len(grid[0])
        dx = [1,0,-1,0]
        dy = [0,1,0,-1]
        for r in range(row):
            for c in range(col):
                if grid[r][c] and (r,c) not in seen:
                    curr = 0
                    stack = [(r,c)]
                    seen.add((r,c))
                    while stack:
                        x,y = stack.pop()
                        curr+=1
                        grid[x][y] = 0
                        for i in range(4):
                            nx,ny = x+dx[i],y+dy[i]
                            if 0<=nx<row and 0<=ny<col and grid[nx][ny] and (nx,ny) not in seen:
                                stack.append((nx,ny))
                                seen.add((nx,ny))
                    ans = max(ans,curr)
        return ans

复杂度分析

时间复杂度：O(MN)，其中 N 为数组长度。
空间复杂度：O(MN)

skinnyh commented 3 years ago

Note

Traverse the grid and use dfs to explore the area of a an island. Mark cells as visited (can be done in place without creating another list)

Solution

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if (i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 0):
                return
            self.area += 1
            grid[i][j] = 0 # mark visited
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                dfs(i + dx, j + dy)

        res = 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                self.area = 0
                dfs(i, j)
                res = max(res, self.area)
        return res

Time complexity: O(MN)

Space complexity: O(MN)

kennyxcao commented 3 years ago

52. 695. Max Area of Island

Intuition

DFS + Mark visited cells

Code

/**
 * @param {number[][]} grid
 * @return {number}
 */
const maxAreaOfIsland = function(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
  const rowSize = grid.length;
  const colSize = grid[0].length;
  const visited = new Set();
  let maxArea = 0;
  for (let r = 0; r < rowSize; r++) {
    for (let c = 0; c < colSize; c++) {
      maxArea = Math.max(maxArea, findArea(r, c, grid, visited));
    }
  }
  return maxArea;
};

function findArea(r, c, grid, visited) {
  if (!inBound(grid, r, c) || grid[r][c] === 0 || visited.has(r * grid[0].length + c)) return 0;
  const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]];
  visited.add(r * grid[0].length + c);
  let area = 1;
  for (const [dr, dc] of dirs) {
    area += findArea(r + dr, c + dc, grid, visited);
  }
  return area;
}

function inBound(grid, r, c) {
  return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
}

Complexity Analysis

Time: O(m * n)
Space: O(m * n)

tongxw commented 3 years ago

思路

小岛问题，二维数组，对四个方向的DFS或者BFS搜索

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int maxArea = 0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
                }
            }
        }

        return maxArea;
    }

    int[] dx = new int[] {1, 0, -1, 0};
    int[] dy = new int[] {0, 1, 0, -1};
    private int dfs(int[][] grid, int row, int col) {
        int count = 0;
        int m = grid.length;
        int n = grid[0].length;
        if (grid[row][col] == 1) {
            ++count;
            grid[row][col] = 2;

            for (int i=0; i<4; i++) {
                int newRow = row + dx[i];
                int newCol = col + dy[i];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    count += dfs(grid, newRow, newCol);
                }
            }
        }

        return count;
    }
}

TC: O(m * n)
SC: O(m * n)

yan0327 commented 3 years ago

思路：本质是DFS深度搜索，然后遇到边界条件返回。然后记住max(a,b) 和 if的差别这里就注意 i<0 || i >= m || j<0 || j>= n|| grid[i][j] == 0 还有就是走过的置0 最后返回是所有岛屿相加值

func maxAreaOfIsland(grid [][]int) int {
    m := len(grid)
    if m == 0{
        return 0
    }
    n := len(grid[0])
    out :=0
    var dfs func(i,j int) int
    dfs = func(i,j int) int{
        if i< 0 || i >= m || j<0 || j>=n{
            return 0
        }
        if grid[i][j] == 0{
            return 0
        }
        grid[i][j] = 0
        top := dfs(i+1,j)
        bottom := dfs(i-1,j)
        left := dfs(i,j-1)
        right := dfs(i,j+1)
        return 1 + top+bottom+left+right
     }
     for i := range grid{
         for j:=range grid[0]{
             out = max(out,dfs(i,j))
         }
     }
     return out
}
func max(a,b int) int{
    if a > b{
        return a
    }else{
        return b
    }
}

时间复杂度：O（LW）L为行数，W为列数空间复杂度：O（LW）

shawncvv commented 3 years ago

思路

DFS深度搜索

代码

Python

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m == 0: return 0
        n = len(grid[0])
        ans = 0
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n: return 0
            if grid[i][j] == 0: return 0
            grid[i][j] = 0
            top = dfs(i + 1, j)
            bottom = dfs(i - 1, j)
            left = dfs(i, j - 1)
            right = dfs(i, j + 1)
            return 1 + sum([top, bottom, left, right])
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j))
        return ans

复杂度

时间复杂度：O(m∗n)
空间复杂度：O(m∗n)

a244629128 commented 3 years ago


var maxAreaOfIsland = function(grid) {
    let ans = 0, n = grid.length, m = grid[0].length
    const trav = (i, j) => {
        if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0
        grid[i][j] = 0
        return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
    }
    for (let i = 0; i < n; i++) 
        for (let j = 0; j < m; j++)
            if (grid[i][j]) ans = Math.max(ans, trav(i, j))
    return ans
};

Menglin-l commented 3 years ago

找到1，用dfs进行上下左右搜索，每次遍历会把与其相连的面积相加，并将其全部置为0

代码部分：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {

        int max = Integer.MIN_VALUE;
        // 寻找下一个岛屿，并比较每个岛屿的大小
        for (int i = 0; i < grid.length; i ++) {
            for (int j = 0; j < grid[0].length; j ++) {
                max = Math.max(max, dfsSearch(grid, i, j));
            }
        }

        return max;
    }

    public int dfsSearch(int[][] grid, int row, int col) {
        if (!isValid(grid, row, col)) return 0;
        grid[row][col] = 0;

        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int island = 1; // 岛屿最小面积为1
        for (int[] dir : dirs) {
            island += dfsSearch(grid, row + dir[0], col + dir[1]);
        }

        return island;
    }

    public boolean isValid(int[][] grid, int row, int col) {
        if (row < 0 || col < 0 || row == grid.length || col == grid[0].length || grid[row][col] == 0) return false;
        else return true;
    }
}

复杂度：

Time: O(row * col)

Space: O(row * col)，递归的最大深度可能是整个grid的大小

freedom0123 commented 3 years ago

class Solution {
    int N  = 55;
    int n,m;
    int dx[] = new int[] {0,-1,0,1};
    int dy[] = new int[] {-1,0,1,0};
    boolean[][] st  = new boolean[N][N];
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        n = grid.length;
        m = grid[0].length;
        for(int i = 0;i < n;i++){
            for(int j  = 0;j < m;j++){
                if(grid[i][j]!=0){
                    ans = Math.max(ans,dfs(i,j,grid));
                }
            }
        }
        return ans;
    }
    public int  dfs(int x,int y,int[][]grid){
        int res  = 1;
        st[x][y] = true;
        for(int  i = 0;i < 4;i++){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a>=n || b<0 || b>=m || grid[a][b]==0) continue;
            if(st[a][b]) continue;
            res += dfs(a,b,grid);
        }
        return res;
    }
}

SunnyYuJF commented 3 years ago

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m=len(grid)
        n=len(grid[0])
        visits=set()
        self.area=0
        def dfs(grid, i, j, area):
            if (i,j) not in visits:
                visits.add((i,j))

                if 0<=i<m and 0<=j+1<n and grid[i][j+1]==1:
                    area = dfs(grid,i,j+1, area+1)
                if 0<=i+1<m and 0<=j<n and grid[i+1][j]==1:
                    area = dfs(grid,i+1,j, area+1)
                if 0<=i-1<m and 0<=j<n and grid[i-1][j]==1:
                    area = dfs(grid,i-1,j, area+1)
                if 0<=i<m and 0<=j-1<n and grid[i][j-1]==1:
                    area = dfs(grid,i,j-1, area+1)
            else:
                area -=1
            return area

        for i in range(m):
            for j in range(n):
                if grid[i][j]==1 and (i,j) not in visits:
                    area = dfs(grid,i,j, 1)
                    self.area = max(self.area, area)

        return self.area

ychen8777 commented 3 years ago

思路

遍历整个grid, 如果相邻格是陆地 ans += dfs(grid, visited, row+delta_row[i], col+delta_col[i]);

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {

        int[][] visited = new int[grid.length][grid[0].length];
        int res = 0;

        //System.out.println(visited[0][0] + " " + visited[1][0]);
        for(int r = 0; r < grid.length; r++) {
            for(int c = 0; c <grid[0].length; c++) {
                res = Math.max(res, dfs(grid, visited, r, c));
            }
        }

        return res;

    }

    private int dfs(int[][] grid, int[][] visited, int row, int col) {
        if (!inArea(grid, row, col) || visited[row][col] == 1 || grid[row][col] == 0) {
            return 0;
        }

        int[] delta_row = {0, 0, 1, -1};
        int[] delta_col = {1, -1, 0, 0};

        int ans = 1;
        visited[row][col] = 1;
        for(int i = 0; i < 4; i++){
            ans += dfs(grid, visited, row+delta_row[i], col+delta_col[i]);
        }

        return ans;

    }

    private boolean inArea(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
    }
}

复杂度

时间: O(r c) \ 空间: O(r c)

shamworld commented 3 years ago

var maxAreaOfIsland = function(grid) {

let row = grid.length, col = grid[0].length;
    function dfs (x, y) {
        if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] === 0) return 0;
        grid[x][y] = 0;
        let ans = 1, dx = [-1, 1, 0, 0], dy = [0, 0, 1, -1];
        for (let i = 0; i < dx.length; i++) {
            ans += dfs(x + dx[i], y + dy[i]);
        }
        return ans;
    }
    let res = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            res = Math.max(res, dfs(i, j));
        }
    }
    return res;

};

ghost commented 3 years ago

题目

Max Area of Island

思路

DFS or BFS

代码


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        res = 0
        m, n = len(grid), len(grid[0])

        def helper(row, col):
            if row<0 or row>=m or col<0 or col>=n or grid[row][col]<=0:
                return 0

            grid[row][col] = -1

            return 1+ helper(row-1, col) + helper(row+1, col) + helper(row, col-1) + helper(row, col+1)

        for i in range(m):
            for j in range(n):
                if grid[i][j]<=0: continue
                res = max(res, helper(i,j))

        return res

复杂度

Space: O(mn) Time: O(mn)

Moin-Jer commented 3 years ago

思路

DFS

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        int ans = 0;
        for (int i = 0; i < row; ++i) {
            for (int j= 0; j < col; ++j) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    int tmp = dfs(grid, i, j, row, col, visited);
                    ans = Math.max(ans, tmp);
                }
            }
        }
        return ans;
    }

    private int dfs(int[][] grid, int i, int j, int row, int col, boolean[][] visited) {
        if (i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || grid[i][j] == 0) {
            return 0;
        }
        int count = 0;
        ++count;
        visited[i][j] = true;
        count += dfs(grid, i - 1, j, row, col, visited);
        count += dfs(grid, i + 1, j, row, col, visited);
        count += dfs(grid, i, j - 1, row, col, visited);
        count += dfs(grid, i, j + 1, row, col, visited);
        return count;
    }
}

复杂度分析

时间复杂度：O(n * m)
空间复杂度：O(n * m)

st2yang commented 3 years ago

思路

dfs

代码

python

class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
            return 0

        grid[i][j] = 0
        top = dfs(i - 1, j)
        down = dfs(i + 1, j)
        left = dfs(i, j - 1)
        right = dfs(i, j + 1)

        return 1 + left + right + top + down

    res = 0
    for i in range(m):
        for j in range(n):
            res = max(res, dfs(i, j))

    return res

复杂度

时间: O(mn)
空间: O(mn)

user1689 commented 3 years ago

题目

https://leetcode-cn.com/problems/max-area-of-island/

思路

DFS

python3

class Solution:
    def maxAreaOfIsland(self, grid) -> int:
        # 参考了@佩奇inging代码发现了原来不通过的问题┭┮﹏┭┮
        def dfs(grid, r, c):
            ans = 1
            # 一进入就需要设置成0 不然会重复计算
            grid[r][c] = 0
            for x, y in[(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
                if (0<=x<len(grid) and 0<=y<len(grid[0])):
                    if grid[x][y] == 1:
                        ans += dfs(grid, x, y)
            return ans

        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    ans = max(dfs(grid, i, j), ans)
        return ans

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        def dfs(x, y):
            if x < 0 or x >= row or y < 0 or y >= col or grid[x][y] != 1:
                return 0
            grid[x][y] = 0
            res = 1
            for newX, newY in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    res += dfs(newX, newY)
            return res

        row = len(grid)
        col = len(grid[0])
        maxSize = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    maxSize = max(dfs(i, j), maxSize)
        return maxSize

复杂度分析

time row * col
space 1

思路

经典岛屿系列，DFS

Python3

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.area = 0
        self.row = len(grid)
        self.col = len(grid[0])

        def dfs(grid, i, j):
            if grid[i][j] != 1: return
            self.area += 1
            grid[i][j] = 2
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            for dx, dy in directions:
                if 0<= i+dx <self.row and 0<=j+dy <self.col:
                    dfs(grid, i+dx, j+dy)

        max_area = 0
        for i in range(self.row):
            for j in range(self.col):
                if grid[i][j] == 1:
                    self.area = 0
                    dfs(grid, i, j)
                    max_area = max(max_area, self.area)

        return max_area

time complexity: O(m *n)，每个点visit一次
space complexity: O(m n)，递归深度最大为O(m n)

ziyue08 commented 3 years ago

/**
 * @param {number[][]} grid
 * @return {number}
 */
var max = 0;
var visited = [];
var fillVisited = function(leni, lenj){
    for(let i = 0; i < leni; i++){
        visited[i] = [];
        for(let j = 0; j < lenj; j++){
            visited[i].push(0);// 全0数组
        }
    }
    return visited;
};
var maxAreaOfIsland = function(grid) {
    let maxx = 0;
    visited = fillVisited(grid.length, grid[0].length);// 行数和列数
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j < grid[0].length; j++){
            if(grid[i][j] == 1){
                max = 0;
                let ans = check(grid, i, j);
                if(maxx < ans){
                    maxx = ans;
                }
            }
        }
    }
    return maxx;
};
var check = function(grid,i,j){
    if(!(i>=0 && i<grid.length && j>=0 && j<grid[0].length)||grid[i][j]!=1||visited[i][j])
        return 0;
    visited[i][j] = 1;
    return check(grid,i,j-1)+check(grid,i,j+1)+ check(grid,i-1,j)+check(grid,i+1,j)+1;
};

ZJP1483469269 commented 3 years ago

题目地址(695. 岛屿的最大面积)

https://leetcode-cn.com/problems/max-area-of-island/

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

 

示例 1：

输入：grid = [[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：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

前置知识

公司

暂无

思路

dfs搜索

关键点

代码

语言支持：Java

Java Code:


class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        boolean[][] flags = new boolean[grid.length][grid[0].length];
        int max = 0;
        for(int i = 0 ;i <grid.length ; i++){
            for(int j = 0 ; j < grid[0].length ; j++){
                max = Math.max(max,dfs(flags,i,j,grid));
            }
        }
        return max;

    }
    public int dfs(boolean[][] flags,int i , int j ,int [][] grid){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0 ;
        if(flags[i][j]) return 0;
        flags[i][j] = true;
        if(grid[i][j]==1){
            return 1 + dfs(flags,i-1 ,j,grid)+dfs(flags,i+1 ,j,grid)+dfs(flags,i ,j-1,grid)+dfs(flags,i ,j+1,grid);
        }else{
            return 0;
        }
    }
}

复杂度分析

令 n 为数组长度。

时间复杂度：$O(nmmax)$max为最大岛屿的面积
空间复杂度：$O(nm)$

Francis-xsc commented 3 years ago

思路

dfs

代码


class Solution {
private:
    int dfs(vector<vector<int>>& grid,int curX,int curY){
        if(curX<0||curY<0||curY==grid[0].size()||curX==grid.size()||grid[curX][curY]!=1)
            return 0;
        grid[curX][curY]=0;
        int dx[]={0,1,0,-1};
        int dy[]={1,0,-1,0};
        int ans=1;
        for(int i=0;i<4;i++){
            ans+=dfs(grid,curX+dx[i],curY+dy[i]);
        }
        return ans;
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans=0;
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();j++){
                    ans=max(ans,dfs(grid,i,j));
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(R×C)。其中 RR 是给定网格中的行数，CC 是列数。
空间复杂度：O(R×C)。

wangzehan123 commented 3 years ago

题目地址(695. 岛屿的最大面积)

https://leetcode-cn.com/problems/max-area-of-island/

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

 

示例 1：

输入：grid = [[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：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

前置知识

公司

暂无

思路

关键点

代码

语言支持：Java

Java Code:


class Solution {
    public static int maxAreaOfIsland(int[][] grid) {
        int max_count = 0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == 1){
                    int current_count = dfs(grid, i, j);
                    if(current_count > max_count) max_count = current_count;
                }
            }
        }
        return max_count;
    }

    public static int dfs(int[][] grid, int i, int j){
        if(i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j] == 0){
            return 0;
        }
        grid[i][j] = 0;
        return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) + dfs(grid, i, j+1) + dfs(grid, i, j-1);
    }
}

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

ChiaJune commented 3 years ago

代码

var maxAreaOfIsland = function(grid) {
  const row = grid.length, col = grid[0].length;
  let res = 0;
  // 深度优先遍历
  const DFS = (i, j) => {
    // 下标越界返回0
    if (i < 0 || i >= row || j < 0 || j >= col) {
      return 0;
    }
    // 值为0返回0
    if(grid[i][j] == 0) return 0;
    // 访问过后置为0，防止重复访问
    grid[i][j] = 0;
    // 递归计算岛屿面积
    return 1 + DFS(i, j-1) + DFS(i-1, j) + DFS(i, j+1) + DFS(i+1, j);
  }
  // 遍历二维数组
  for(let i=0; i<row; i++) {
    for(let j=0; j<col; j++) {
      if (grid[i][j] == 1) {
        res = Math.max(res, DFS(i,j));
      } else {
        continue;
      }
    }
  }
  return res;
};

复杂度

时间：O(mn) 空间：O(mn)

xieyj17 commented 3 years ago

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        res = 0

        def dfs(r, c):
            if (r<0 or r>=m) or (c<0 or c>=n):
                return 0
            if grid[r][c] == 0:
                return 0

            if grid[r][c] == 1:
                grid[r][c] = 0                        
                return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r, c-1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    res = max(res, dfs(i,j))
        return res

Using DFS
If we hit the boundary, return 0
If the searched point is 0, return 0
Otherwise, marked the visited point by 0, and calculated the area of four surrounding squares using recursive

Time: O(m*n)

Space: O(m*n)

akxuan commented 3 years ago

思路用 dfs, 把visit 过的cell 改成0 看着很简单, 但是做到还是不容易. 尽量少些判断, 我的第一个solution 巨多判断, 就很伤时间复杂度 O(MN) 空间(MN)

solution 2

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j]:
                grid[i][j] = 0

                return 1 + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i + 1, j) + dfs(i, j - 1)
            return 0
        maximum = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    maximum = max(dfs(i,j),maximum)

        return maximum

Solution 1:


        '''

        def action(grid, x,y):
            res = []

            for r,c in [ (x-1,y), (x+1,y), (x, y+1), (x,y-1)]:

                if   r>=0 and r< len(grid) and  c>=0 and c< len(grid[0])  and grid[r][c] == 1:
                    res.append((r,c))

            return res

        def dfs( grid, x, y, curr, res):

            if grid[x][y] == 0 :
                return 

            if len(action(grid,x,y))==0  and curr>0 :
                res.append(curr)

            print((x,y,action(grid,x,y)))
            grid[x][y] = 0        
            for r, c in action(grid,x,y) :

                dfs(grid, r, c, curr+1, res)

        res = []
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:

                    dfs(grid,r,c,1,res)
        if res:        return max(res)
        else: return 0
        '''

leetcode-pp / 91alg-5-daily-check

【Day 50 】2021-10-29 - 695. 岛屿的最大面积 #68

695. 岛屿的最大面积

入选理由

题目地址

前置知识

题目描述

思路:

方法: flood fill算法(dfs版)

代码

复杂度分析

思路

语言

代码

复杂度分析

思路

关键点

代码

thoughts

code

complexity

思路

Java Code

时间&空间

思路

代码

复杂度

695. 岛屿的最大面积

思路一

代码

语言 CSharp

Day 50: 695. Max Area of Island (search, DFS, BFS)

思路

代码

link:

代码 Javascript

复杂度分析

思路

代码

复杂度

经典dfs

Intuition

Implementation

Complexity

Complexity Time O(m n) Space O(m n)

Idea:

Code:

Complexity:

Idea

Python Code

思路

代码

思路

Complexity

思路

代码

Note

Solution

52. 695. Max Area of Island

Intuition

Code

Complexity Analysis

思路

代码

思路

代码

找到1，用dfs进行上下左右搜索，每次遍历会把与其相连的面积相加，并将其全部置为0

代码部分：

复杂度：

Time: O(row * col)

Space: O(row * col)，递归的最大深度可能是整个grid的大小

思路

代码

复杂度

题目

思路

代码

复杂度

思路

代码