题目
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.
题目地址
讲解
一看这题我首先想到的就是并查集，只不过我们需要稍作改动，我们需要知道每个并查集的元素大小，所以我加入了一个 size 属性，而为了节省空间去掉了 value 属性。另外，我们还需要一个空间来存储 DS 结点，而且最好是很快的取出，所以我使用了 hashmap 来存，但 key 是一个整数元组（tuple），但 java 不能很方便的使用 tuple，所以我直接变相的使用字符串来实现 Key。
java 代码
class Solution {
public int maxAreaOfIsland(int[][] grid) {
Map<String, DS> map = new HashMap<>();
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j]==1){
DS ds = new DS(1);
map.put(i+”,”+j, ds);
if(i-1>=0 && grid[i-1][j]==1){
ds.union(map.get((i-1)+”,”+j), ds);
}
if(j-1>=0 && grid[i][j-1]==1){
ds.union(map.get(i+”,”+(j-1)), ds);
}
}
}
}
int result = 0;
for(String s:map.keySet()){
int size = map.get(s).find().size;
if(result<size){
result = size;
}
}
return result;
}
class DS{
// private int value;
private DS parent;
private int rank;
private int size;
public DS(int value){
// this.value = value;
rank = 0;
parent = this;
size = 1;
}
public DS find(){
if(this.parent!=this){
this.parent = this.parent.find();
}
return this.parent;
}
public void union(DS x, DS y){
DS xParent = x.find();
DS yParent = y.find();
if(xParent==yParent){
return;
}
if(xParent.rank>yParent.rank){
yParent.parent = xParent;
xParent.size += yParent.size;
}else if(xParent.rank<yParent.rank){
xParent.parent = yParent;
yParent.size += xParent.size;
}else{
xParent.parent = yParent;
yParent.size += xParent.size;
yParent.rank++;
}
}
}
}