Comment on page

695.Max-Area-of-Island

695. Max Area of Island

题目地址

题目描述

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
​
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
​
Example 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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
​
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
​
Note: The length of each dimension in the given grid does not exceed 50.

代码

Approach #1 DFS

class Solution {
public int maxAreaOfIsland(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
boolean seen = new boolean[R][C];
int ans = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
ans = Math.max(ans, area(r, c, seen, grid));
}
}
return ans;
}
​
private int area(int r, int c, boolean[][] seen, int[][] grid) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
|| seen[r][c] || grid[r][c] == 0) {
return 0;
}
seen[r][c] = true;
return (1 + area(r + 1, c, seen, grid)
+ area(r - 1, c, seen, grid)
+ area(r, c - 1, seen, grid)
+ area(r, c + 1, seen, grid));
}
​
}

Approach #2 DFS Iterative

class Solution {
public int maxAreaOfIsland(int[][] grid) {
boolean[][] seen = new boolean[grid.length][grid[0].length];
int[] dr = new int[]{1, -1, 0, 0};
int[] dc = new int[]{0, 0, 1, -1};
​
int ans = 0;
for (int r0 = 0; r0 < grid.length; r0++) {
for (int c0 = 0; c0 < grid[0].length; c0++) {
if (grid[r0][c0] == 1 && !seen[r0][c0]) {
​
int shape = 0;
Stack<int[]> stack = new Stack();
stack.push(new int[]{r0, c0});
seen[r0][c0] = true;
while (!stack.empty()) {
int[] node = stack.pop();
int r = node[0], c = node[1];
shape++;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < grid.length &&
0 <= nc && nc < grid[0].length &&
grid[nr][nc] == 1 && !seen[nr][nc]) {
stack.push(new int[]{nr, nc});
seen[nr][nc] = true;
}
}
}
ans = Math.max(ans, shape);
}
}
}
return ans;
}
}