### 题目

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.

### Union Find

#### 代码

class Solution {
private int[] count = new int; // 分组成员数量表（下标为小组ID）
private int[] board = new int; // 分组ID表（下标为小组ID，值于下标相等的点为根节点）

private void init(int[][] grid) {
int height = grid.length;
int width = grid.length;
count = new int[height * width + 1];
board = new int[height * width + 1];
}
public int maxAreaOfIsland(int[][] grid) {
int height = grid.length;
if (height == 0) { return 0; }
int width = grid.length;
init(grid);
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (grid[i][j] == 1) {
int posCurr = j+1 + width * i, posLeft = -1, posUpper = -1;
create(posCurr);
if (j > 0 && grid[i][j-1] == 1) {
posLeft = j + width * i;
merge(posCurr,posLeft); // 当前树嫁接到左树
}
if (i > 0 && grid[i-1][j] == 1) {
posUpper = j+1 + width * (i-1);
merge(posCurr,posUpper); // 当前树嫁接到上树
}
}
}
}
int max = 0;
for (int i = 1; i < count.length; i++) {
max = Math.max(max,count[i]);
}
return max;
}
private void create(int pos) {
board[pos] = pos;
count[pos] = 1;
}
private int find(int pos) {
if (board[pos] == pos) {
return pos;
} else {
int root = find(board[pos]);
board[pos] = root; // path compression
return root;
}
}
// root1嫁接到root2上
private void merge(int pos1, int pos2) {
int root1 = find(pos1);
int root2 = find(pos2);
if (root1 != root2) {
board[root1] = board[root2];
count[root2] += count[root1];
count[root1] = 0;
}
}
}


#### 结果 