岛屿最大面积 one pass 解法求解

bigboss789 发表于 2021-4-12 05:23
如果只有一个岛是可以的。但是题目里会有多个岛。

多谢多谢！这个居然没有考虑到，好像除了Two Pass之后只可能Union Find了

HughHe 发表于 2021-4-12 05:46
用union-find algorithm，记录每个union的sz和最大的sz，one pass。加上shortcut的trick之后，复杂度O(n*lo ...

恩，我觉得uf可行。

遍历整个数组， 边界的0和外围（比如id=-1）connect。 非边界1和up，left 1 connect。
不过遇到非边界的0，怎么处理，我还是不太清楚。。。

如果你方便提供一小段示范代码那是最好，哈哈

能问下lc题号吗

bigboss789 发表于 2021-04-11 19:33:31
恩，我觉得uf可行。

遍历整个数组， 边界的0和外围（比如id=-1）connect。 非边界1和up，left 1 connect。

我试着手写了一下，确实在边界上的处理比较模糊，但是我觉得这是题目本身的问题。此题有两种理解。

1）如果所有岛都是字面意义的“岛”，那么岛四周都是水，边界就不会有岛。这个情况下，我们依次遍历每行。（a）把第一行直连接到一个海的root上。（b）之后每个block，如果是水，就检查是否和海相连； 陆地就相互连接。（c）内湖的情况可以在封口的时候检查一块陆地的正上方是水且和海不相连，那它就是内湖。这个union计入陆地。（d）其他都可以按照标准uf处理。一次遍历就够了。

2）如果边界上有陆地就确实很麻烦，需要面试官澄清这几个corner case：
a） 如果board的边界全是land，那么是不是就没有海
b）如果board有一行全是海，那么哪边是湖，哪边是海？小的是湖？
c）一个board上只有一个角格是水，那它是海还是湖？
考虑到corner case这么恶心人，这就不是一个很好的面试题了。所以面试的时候考虑情况（1）就好。

bbbnnn777 发表于 2021-4-12 10:39
能问下lc题号吗

没有原题。只有一条类似的， 尔拜。

并查集应该是one pass