05 August 2008
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:
1
2
3
4
5
6
7
8
[[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:
1
[[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.
典型的DFS，对每个元素，如果是1的话就前后左右调用递归递归，然后比较每个元素的最大值；如果想避免修改原本的数组，可以另外新建一个同等大小的二维数组来记录是否访问过，由于要同时记录多个元素是否被访问过，因此不能像79 Word Search那样优化空间。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, 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;
}
private int dfs(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
grid[i][j] = 0;//这一步很重要，设为0是为了防止递归过程中对当前元素的重复调用
//本身的面积+四个方向可能的面积
return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}
return 0;
}
}
不改变原本的二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return maxArea;
}
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, dfs(grid, rows, cols, i, j, visited)); // 比较最大岛屿
visited[i][j] = false; //把设成true的值改回来，对这道题来说，可以不用这步
}
}
}
return maxArea;
}
private int dfs(int[][] grid, int rows, int cols, int x, int y, boolean[][] visited) {
if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] != 1 || visited[x][y]) {
return 0;
}
int currArea = 1; //当前岛屿
visited[x][y] = true;
currArea += dfs(grid, rows, cols, x - 1, y, visited);
currArea += dfs(grid, rows, cols, x + 1, y, visited);
currArea += dfs(grid, rows, cols, x, y - 1, visited);
currArea += dfs(grid, rows, cols, x, y + 1, visited);
return currArea; //递归栈中返回当前的面积
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int maxArea = 0;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = false;
}
}
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, visited));
visited[i][j] = false;//重设刚才的元素为下一轮检查做准备
}
}
}
return maxArea;
}
private int dfs(int[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length, n = grid[0].length;
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1 && !visited[i][j]) {
visited[i][j] = true;
//本身的面积+四个方向可能的面积
return 1 + dfs(grid, i + 1, j, visited) + dfs(grid, i - 1, j, visited) + dfs(grid, i, j + 1, visited) + dfs(grid, i, j - 1, visited);
}
return 0;
}
}
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private static int[][] DIRECTIONS = new int[][]{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
// BFS
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int M = grid.length;
int N = grid[0].length;
boolean[][] visited = new boolean[M][N];
int res = 0;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
res = Math.max(res, bfs(grid, visited, i, j));
}
}
}
return res;
}
private int bfs(int[][] grid, boolean[][] visited, int i, int j) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{i, j});
visited[i][j] = true;
int res = 0;
while (!q.isEmpty()) {
int[] curr = q.poll();
res++;
for (int[] dir: DIRECTIONS) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || visited[x][y] || grid[x][y] != 1) continue;
q.add(new int[]{x, y});
visited[x][y] = true;
}
}
return res;
}
}
BFS也可以改变元素，不用visited
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
private final int[][] dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
public int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return maxArea;
}
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, bfs(grid, i, j, rows, cols));
}
}
}
return maxArea;
}
private int bfs(int[][] grid, int x, int y, int rows, int cols) {
int currMaxArea = 0;
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{x, y});
grid[x][y] = -1; // 沉岛思想,记住元素入栈时就要改变访问状态
while (!queue.isEmpty()) {
int[] curr = queue.poll();
currMaxArea++;
for (int[] dir : dirs) {
int newX = dir[0] + curr[0];
int newY = dir[1] + curr[1];
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 1) {
queue.offer(new int[]{newX, newY});
grid[newX][newY] = -1; // 同样，元素入栈时就要改变访问状态
}
}
}
return currMaxArea;
}
}
Union Find
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
private static int[][] DIRECTIONS = new int[][]{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int M = grid.length;
int N = grid[0].length;
int res = 0;
UinionFind uf = new UinionFind(grid);
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++) {
if (grid[i][j] == 1) {
res = Math.max(res, link(grid, i, j, uf, M, N));
}
}
}
return res;
}
private int link(int[][] grid, int i, int j, UinionFind uf, int M, int N) {
int pre = i * N + j;
int res = uf.getSize(pre);
for (int[] dir: DIRECTIONS) {
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || y < 0 || x >= M || y >= N || grid[x][y] != 1) continue;
res = Math.max(res, uf.union(pre, x * N + y));
}
return res;
}
class UinionFind {
int[] parent;
int[] size;
int[] rank;
UinionFind(int[][] grid) {
int M = grid.length;
int N = grid[0].length;
this.parent = new int[M * N];
for (int i=0; i<M*N; i++) this.parent[i] = i;
this.rank = new int[M * N];
this.size = new int[M * N];
Arrays.fill(this.size, 1);
}
int find(int x) {
if (this.parent[x] != x) {
this.parent[x] = find(this.parent[x]);
}
return this.parent[x];
}
int union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return this.size[px];
if (this.rank[px] > this.rank[py]) {
this.parent[py] = px;
this.size[px] = this.size[px] + this.size[py];
return this.size[px];
} else if (this.rank[px] < this.rank[py]) {
this.parent[px] = py;
this.size[py] = this.size[px] + this.size[py];
return this.size[py];
} else {
this.parent[px] = py;
this.rank[py]++;
this.size[py] = this.size[px] + this.size[py];
return this.size[py];
}
}
int getSize(int x) {
return this.size[find(x)];
}
}
}