【Day 50 】2022-12-20 - 695. 岛屿的最大面积

[azl397985856]

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

[Abby-xu]

class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: def dfs(x,y): if grid[x][y] == 1: grid[x][y] = -1 res = 1 else: return 0 if x + 1 < len(grid): res += dfs(x+1,y) if x - 1 >= 0: res += dfs(x-1,y) if y + 1 < len(grid[0]): res += dfs(x,y+1) if y - 1 >= 0: res += dfs(x,y-1) return res

    seen = set()
    max_area = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                max_area = max(max_area, dfs(i,j))

    return max_area

[yuxiangdev]

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int maxArea = 0;
        int area;
        boolean[][] visited = new boolean[m][n];

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

        return maxArea;
    }

    private int dfs(int[][] grid, int x, int y, boolean[][] visited) {
        int m = grid.length;
        int n = grid[0].length;
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1 || visited[x][y]) {
            return 0;
        }

        visited[x][y] = true;
        int area = 1;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] dir : directions) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            area += dfs(grid, nx, ny, visited);
        }

        return area;
    }

Time O(mn) Space O(mn)

[chenming-cao]

解题思路

DFS。对二维数组进行遍历，遇到陆地（值为1）的时候开始DFS搜索周围4个方向，看是否有连成片的陆地，同时将该位置的值设为0，记为已经访问过，避免重复。以此为基础将DFS进行下去，直到周围没有陆地为止，这样就求出了陆地的面积。遍历的时候不断更新最大值。遍历结束返回即为结果。

代码

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

    private int dfs(int[][] grid, int row, int col) {
        int m = grid.length, n = grid[0].length;
        // index not valid
        if (row < 0 || row >= m || col < 0 || col >= n) return 0;
        // visited or in water
        if (grid[row][col] == 0) return 0;
        // marked current land as visited
        grid[row][col] = 0;
        return 1 + dfs(grid, row - 1, col) + dfs(grid, row + 1, col) + dfs(grid, row, col - 1) + dfs(grid, row, col + 1);
    }
}

复杂度分析

• 时间复杂度：O(m * n)，遍历整个数组，每次dfs操作为O(1)
• 空间复杂度：O(m * n)

[ringo1597]

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for (int i = 0; i != grid.length; ++i) {
            for (int j = 0; j != grid[0].length; ++j) {
                int cur = 0;
                Deque<Integer> stacki = new LinkedList<Integer>();
                Deque<Integer> stackj = new LinkedList<Integer>();
                stacki.push(i);
                stackj.push(j);
                while (!stacki.isEmpty()) {
                    int cur_i = stacki.pop(), cur_j = stackj.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int[] di = {0, 0, 1, -1};
                    int[] dj = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        stacki.push(next_i);
                        stackj.push(next_j);
                    }
                }
                ans = Math.max(ans, cur);
            }
        }
        return ans;
    }
}

[snmyj]

class Solution {

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

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length) {
            return 0;
        }
        if (j < 0 || j >= grid[0].length) {
            return 0;
        }

        if (grid[i][j] == 1) {
            int ans = 1;
            grid[i][j] = 0;
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (int[] dir : dirs) {
                ans += dfs(grid, i + dir[0], j + dir[1]);
            }
            return ans;
        }
        return 0;
    }
}

[Alyenor]

function maxAreaOfIsland(grid: number[][]): number {
    let n=grid.length,
    m=grid[0].length,
    g=grid,
    res=0
    const dx=[-1,0,1,0],dy=[0,1,0,-1]
    const dfs=(x,y)=>{
        let tmp=1
        g[x][y]=0
        for(let i=0;i<4;i++){
            let a=dx[i]+x,b=dy[i]+y
            if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]===1){
               tmp += dfs(a,b)
            }
        }
        return tmp
    }
    for(let i=0;i<n;i++){
        for(let j=0;j<m;j++){
            if(g[i][j]===1){
                res=Math.max(res, dfs(i,j))
            }
        }
    }
    return res
};

[bookyue]

1. union find
2. dfs

code

class Solution {
    private final static int[][] dirs = {{1, 0}, {0, 1}};
    private int[] parent;
    private int[] size;
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (m == 1 && n == 1) return grid[0][0];

        parent = new int[m * n];
        size = new int[m * n];
        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) continue;

                ans = Math.max(ans, grid[i][j]);

                for (int[] dir : dirs) {
                    int i2 = i + dir[0];
                    int j2 = j + dir[1];

                    if (i2 >= 0 && i2 < m && j2 >= 0 && j2 < n && grid[i2][j2] == 1)
                        ans = Math.max(ans, union(i * n + j, i2 * n + j2));
                }
            }
        }

        return ans;
    }

    private int find(int p) {
        if (parent[p] != p) parent[p] = find(parent[p]);
        return parent[p];
    }

    private int union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return size[pRoot];

        if (size[pRoot] >= size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
            return size[pRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
            return size[qRoot];
        }
    }
}

    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int maxArea = 0;

        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == 1)
                    maxArea = Math.max(maxArea, getArea(grid, i, j));

        return maxArea;
    }

    private int getArea(int[][] grid, int x, int y) {
        grid[x][y] = 0;
        int area = 1;

        for (int[] dir : DIRS) {
            int x1 = x + dir[0];
            int y1 = y + dir[1];

            if (x1 >= 0 && x1 < grid.length && y1 >= 0 && y1 < grid[0].length
                    && grid[x1][y1] == 1)
                area += getArea(grid, x1, y1);
        }

        return area;
    }

[testplm]

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        maxArea = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
               if grid[i][j] == 1:  # run dfs only when we find a land
                    maxArea = max(maxArea, self.dfs(grid, i, j))
        return maxArea

    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != 1:
            return 0
        maxArea = 1
        grid[i][j] = '#'  
        maxArea += self.dfs(grid, i+1, j)
        maxArea += self.dfs(grid, i-1, j)
        maxArea += self.dfs(grid, i, j+1)
        maxArea += self.dfs(grid, i, j-1)

        return maxArea

[mayloveless]

思路

找到为1的节点，深度遍历，访问过的点位计数，最后取最大。

代码

var maxAreaOfIsland = function(grid) {
    const h = grid.length
    const w = grid[0].length
    const visited = Array(h).fill().map(() => Array(w).fill(false))
    let count = 0;
    const dfs = (i, j) => {
        visited[i][j] = true
        let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]// 试探
        for (let k = 0; k < 4; ++k) {
            let newi = i + directions[k][0]
            let newj = j + directions[k][1]
            if (newi >= 0 && newi < h && newj >= 0 && newj < w
                && visited[newi][newj] == false && grid[newi][newj] == '1') {
                dfs(newi, newj)
                count ++;// 访问过的+1
            }
        }
    }

    let max = 0
    for (let i = 0; i < h; ++i) {
        for (let j = 0; j < w; ++j) {
            if (visited[i][j] != true && grid[i][j] == '1') {// 从有值的点开始dfs
                count = 1;// 每次重新计数
                dfs(i, j);
                max = Math.max(count, max);
            }
        }
    }

    return max
};

复杂度

时间：O(wh) 空间：O(wh)

[JancerWu]

class Solution {
    int ans = 0;
    int[][] move = {{-1,0},{1,0},{0,-1},{0,1}};
    int[] tmp = new int[1];
    int m, n;
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length; n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    tmp[0] = 0;
                    dfs(i, j, tmp, visited, grid);
                }
            }
        }
        return ans;
    }
    public void dfs(int i, int j, int[] s, boolean[][] visited, int[][] grid) {
        visited[i][j] = true;
        grid[i][j] = 0;
        s[0]++;
        ans = Math.max(ans, s[0]);
        for (int[] mv : move) {
            int x = i + mv[0], y = j + mv[1];
            if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && grid[x][y] == 1) {
                dfs(x, y, s, visited, grid);
            }
        }
    }
}
// 做成了麻花

[zywang0]

    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int maxArea = 0;

        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == 1)
                    maxArea = Math.max(maxArea, getArea(grid, i, j));

        return maxArea;
    }

    private int getArea(int[][] grid, int x, int y) {
        grid[x][y] = 0;
        int area = 1;

        for (int[] dir : DIRS) {
            int x1 = x + dir[0];
            int y1 = y + dir[1];

            if (x1 >= 0 && x1 < grid.length && y1 >= 0 && y1 < grid[0].length
                    && grid[x1][y1] == 1)
                area += getArea(grid, x1, y1);
        }

        return area;
    }

[yuexi001]

class Solution {
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) {
                int cur = 0;
                queue<int> queuei;
                queue<int> queuej;
                queuei.push(i);
                queuej.push(j);
                while (!queuei.empty()) {
                    int cur_i = queuei.front(), cur_j = queuej.front();
                    queuei.pop();
                    queuej.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {0, 0, 1, -1};
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        queuei.push(next_i);
                        queuej.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

[heng518]

class Solution { public: int gridArea(vector<vector>& grid, int i, int j){ if( i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1){ grid[i][j] = 0; return 1 + gridArea(grid, i+1, j) + gridArea(grid, i-1, j) + gridArea(grid, i, j-1) + gridArea(grid, i, j+1); } return 0; }

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int res = 0;
    for(int i = 0; i < grid.size(); i++)
        for(int j = 0; j < grid[0].size(); j++)
            if(grid[i][j] == 1)
                res = max(max_area, gridArea(grid, i, j));
    return res;
}

};

[RestlessBreeze]

代码

class Solution {
    int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
            return 0;
        }
        grid[cur_i][cur_j] = 0;
        int di[4] = {0, 0, 1, -1};
        int dj[4] = {1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        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;
    }
};

[A-pricity]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    const gLen = grid.length
    if (!gLen) {
        return 0
    }
    const hLen = grid[0].length
    // 存储当前所选元素在平面内上下左右四个方向元素
    const d = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    // 维护递归过程中，平面中元素的使用状态，每个只能使用一次
    const used = []
    // 保存岛屿最大面积
    let max = 0
    let count = 0
    // 判断所选元素是否在二维平面内
    const inArea = function (x, y) {
        return x >=0 && x < grid.length && y >=0 && y < grid[0].length
    }
    // 递归函数，深度优先遍历，从grid[i][j]开始移动，将所有链接的陆地标记为访问过
    const dfs = function (grid, i, j) {
        used[i][j] = true
        count ++
        for (let k = 0; k < 4; k++) {
            const newX = i + d[k][0]
            const newY = j + d[k][1]
            if (inArea(newX, newY) && !used[newX][newY] && grid[newX][newY] == 1) {
                dfs(grid, newX, newY)
            }
        }
    }
    for (let i = 0; i < gLen; i++) {
        used.push(new Array(hLen).fill(false))
    }
    for (let i = 0; i < gLen; i++) {
        for (let j = 0; j < hLen; j++) {
            if (!used[i][j] && grid[i][j] == 1) {
                dfs(grid, i, j)
                max = Math.max(max, count)
                count = 0
            }
        }
    }
    return max
};

[Dou-Yu-xuan]

思路：

我们可以使用深度优先搜索来解决这个问题。

在深度优先搜索中，我们从起点开始，沿着一条路径一直搜索直到无法继续为止，然后回溯并探索另一条路径。这种方法使我们能够找到所有从起点可到达的点，也就是岛屿的所有部分。

我们可以定义一个递归函数，每次调用它的时候传入当前点的行和列作为参数。然后我们检查这个点是否是 1，如果是，我们将其设置为 0，并将这个点作为新的起点调用递归函数，探索其 上下左右的点。这样我们就能够遍历整个岛屿，并将它标记为已探索过。

为了计算岛屿的面积，我们可以在递归函数中计数器加 1。最后，我们可以遍历整个网格，找到所有未被探索过的 1，并使用递归函数计算每个岛屿的面积，返回最大的面积即可。

代码

 class Solution:
     def dfs(self,grid,cur_i,cur_j):
         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
        ans = 1
        for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:
            next_i,next_j = cur_i+di,cur_j+dj
           ans += self.dfs(grid,next_i,next_j)
        return ans

    def maxAreaOfIsland(self, grid) :
       ans =0
       for i,l in enumerate(grid):
            for j,n in enumerate(l):
                ans = max(self.dfs(grid,i,j),ans)
       return ans

[Jetery]

695. 岛屿的最大面积

思路

dfs

代码 (cpp)

class Solution {
public:

    int ans = 0, row, col;
    int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();
        vector<vector<bool>> vis(row, vector<bool>(col, false));
        for (int i = 0; i < row; i++) 
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1 && !vis[i][j])
                    ans = max(ans, dfs(i, j, grid, vis));
            }
        return ans;
    }
    int dfs(int i, int j, vector<vector<int>>& grid, vector<vector<bool>>& vis) {
        if (i < 0 || j < 0 || i == row || j == col || vis[i][j]) return 0;
        int area = 0;
        if (grid[i][j] == 1) {
            vis[i][j] = true;
            area++;
            for (auto dir : dirs) {
                int x = i + dir[0];
                int y = j + dir[1];
                area += dfs(x, y, grid, vis);
            }
        }
        return area;
    }
};

复杂度分析

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

[GG925407590]

class Solution {
    int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
            return 0;
        }
        grid[cur_i][cur_j] = 0;
        int di[4] = {0, 0, 1, -1};
        int dj[4] = {1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        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;
    }
};

[chiehw]

struct Point{
    int x;
    int y;
    Point(int x, int y): x(x), y(y) {}
};
int MATRIX_X[4] = {0, 0, 1, -1};
int MATRIX_Y[4] = {1, -1, 0, 0};

class Solution {
private:
    bool is_land(const vector<vector<int>> &grid, const Point &point){
        return grid[point.x][point.y] == 1;
    }

    bool is_in_grid(const vector<vector<int>> &grid, const Point &point){
        return point.x >= 0 && point.y >= 0 && point.x < grid.size() && point.y < grid[0].size();
    }

    void add_around_point_to_queue(const vector<vector<int>> &grid, Point &point, queue<Point> &q){
        int x, y;
        for (int index = 0; index != 4; ++index) {
            int x = point.x + MATRIX_X[index];
            int y = point.y + MATRIX_Y[index];
            q.push(Point(x, y));
        }
    }

    int bfs(vector<vector<int>> &grid, Point &startPoint){
        queue<Point> q;
        q.push(startPoint);

        int area = 0;
        while (!q.empty()) {
            Point point = q.front();
            q.pop();

            if (is_in_grid(grid, point) && is_land(grid, point)){
                grid[point.x][point.y] = 0;
                add_around_point_to_queue(grid, point, q);
                area++;
            }
        }
        return area; 
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        int cur;
        for (int x = 0; x != grid.size(); x++) {
            for (int y = 0; y != grid[0].size(); y++) {
                Point point = Point(x, y);
                cur = bfs(grid, point);
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

[klspta]

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

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

[wtdcai]

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
        ans = 1
        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            next_i, next_j = cur_i + di, cur_j + dj
            ans += self.dfs(grid, next_i, next_j)
        return ans

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, l in enumerate(grid):
            for j, n in enumerate(l):
                ans = max(self.dfs(grid, i, j), ans)
        return ans

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
 //定义一个表示岛屿的面积
        int max = 0;
        //这两个for循环是来遍历整张二维格上的所有陆地的。
        //i 表示行，j表示列
        for(int i = 0;i<grid.length;i++){
            for(int j = 0; j<grid[0].length;j++){
                //陆地的格
                if(grid[i][j]==1){
                    //取出最大的面积
                    max = Math.max(max,dfs(grid,i,j));
                }  
            }
        }
        //返回最大的陆地面积
        return max;
    }
    public 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;
       //定义一个变量表示岛屿的面积，就是包含几个陆地
        int sum = 1;
        //将陆地改为海洋，防止重复陆地重复遍历。
        grid[i][j] =0;
        //遍历上方元素，每遍历一次陆地就加一
        sum += dfs(grid,i+1,j);
        //遍历下方元素
        sum +=dfs(grid,i-1,j);
        //遍历右边元素
        sum +=dfs(grid,i,j+1);
        //遍历左边元素
        sum += dfs(grid,i,j-1);
        return sum;
    }
}

[saitoChen]

思路

先找到1这个点，然后递归去找四周的点，计算总和

代码

const maxAreaOfIsland = (grid) => {
  let x = grid.length, y = grid[0].length, count = 0
  for (let i = 0; i < x; i++) {
    for (let j = 0; j < y; j++) {
      if (grid[i][j] === 1) {
        count = Math.max(count, calclucateIsland(grid, x, y, i, j))
      }
    }
  }
  return count
}

const calclucateIsland = (grid, x, y, i, j) => {
  // 处在不可能成为岛或者不是1的情况
  if (i >= x || i < 0 || j >= y || j < 0 || grid[i][j] === 0) return 0
  let num = 1
  // 需要把当前点标为0，不然遍历四周节点时又会计算回这个点导致无限循环
  grid[i][j]=0;
  num += calclucateIsland(grid, x, y, i + 1, j)
  num += calclucateIsland(grid, x, y, i - 1, j)
  num += calclucateIsland(grid, x, y, i, j + 1)
  num += calclucateIsland(grid, x, y, i, j - 1)

  return num
}

复杂度分析

时间复杂度：O(N^2)

[Alexno1no2]

# 遍历二维数组，对于每块土地，去其前后左右找相邻土地，再去前后左右的土地找其前后左右的土地，直到周围没有土地
# 对于每一块已找过的土地，为避免重复计算，将其置为0
# 遍历所有的岛屿，然后取这些岛屿的最大面积res = max(res, dfs(i, j))

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 + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
            return 0

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

[FlipN9]

/**
    dfs 返回值记录 淹没土地的个数
    TC: O(RC)   SC: O(RC)
*/
class Solution {
    int[][] grid;
    int R, C;
    boolean[][] visited;

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;

        this.grid = grid;
        this.R = grid.length;
        this.C = grid[0].length;
        this.visited = new boolean[R][C];

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

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

[paopaohua]

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] != 0){
                    int[] cur_max = new int[1];
                    dfs(grid,i,j,cur_max);
                    maxArea = Math.max(cur_max[0],maxArea);
                }
            }
        }
        return maxArea;
    }
    public void dfs(int[][] grid,int row,int col,int[] curArea){
        if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0){
            return;
        }
        grid[row][col] = 0;
        curArea[0] += 1;
        // 上下左右
        dfs(grid,row -1,col,curArea);
        dfs(grid,row +1,col,curArea);
        dfs(grid,row,col + 1,curArea);
        dfs(grid,row,col - 1,curArea);
    }
}

[tiandao043]

思路

并查集，维护秩，用了并查集模板

代码

class UnionFind
{
    private:
        vector<int> father;
        vector<int> rank;//按秩合并
        vector<int> area;
        int ans;
    public:
        UnionFind(vector<vector<int> >& grid)
        {
            ans=0;
            int row=grid.size(),col=grid.front().size();
            father.assign(row*col,0);
            rank.assign(row*col,0);
            area.assign(row*col,1);
            for(int i=0;i<row;++i)
            for(int j=0;j<col;++j)
            {
                if(grid[i][j]==1)
                ans=1;
                father[i*col+j]=i*col+j;
            }
        }
        int find(int x)
        {
            return x==father[x]?x:(father[x]=find(father[x]));//路径压缩
        }
        void Union(int x,int y)//按秩合并
        {
            int fx=find(x),fy=find(y);
            if(fx==fy)
            return;
            if(rank[fx]>rank[fy])
            {
                father[fy]=fx;
                area[fx]+=area[fy];
            }
            else if(rank[fy]>rank[fx])
            {
                father[fx]=fy;
                area[fy]+=area[fx];
            }
            else
            {
                area[fx]+=area[fy];
                father[fy]=fx;
                ++rank[fx];
            }
            ans=max(ans,max(area[fy],area[fx]));
        }
        int solve()
        {
            return ans;
        }
};

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if(grid.empty()||grid.front().empty())return 0;
        UnionFind uf(grid);
        int r=grid.size(),c=grid[0].size();
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(grid[i][j]==1){
                    grid[i][j]==0;
                    if(i>0&&grid[i-1][j]==1)uf.Union(i*c+j,(i-1)*c+j);
                    if(i<r-1&&grid[i+1][j]==1)uf.Union(i*c+j,(i+1)*c+j);
                    if(j>0&&grid[i][j-1]==1)uf.Union(i*c+j,i*c+j-1);
                    if(j<c-1&&grid[i][j+1]==1)uf.Union(i*c+j,i*c+j+1);
                }
            }
        }
        return uf.solve();
    }
};

[whoam-challenge]

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 ans = 1 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: next_i, next_j = cur_i + di, cur_j + dj ans += self.dfs(grid, next_i, next_j) return ans

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    ans = 0
    for i, l in enumerate(grid):
        for j, n in enumerate(l):
            ans = max(self.dfs(grid, i, j), ans)
    return ans

[neado]

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

[Elsa-zhang]

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

        m,n = len(grid), 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