我在练习面试时，在 Glassdoor 上发现了以下问题。
Given a board with black (1) and white (0), black are all connected. find the min rectangle that contains all black. An example given is
0 0 0 0 0
0 1 1 1 0
0 1 1 0 0
0 1 0 0 0
0 0 0 0 0
这个问题挑战了我对连通性的理解，下面矩阵中的1会被认为是相互连通的吗？
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
我应该默认考虑 8 个连通性吗？
最佳答案
默认情况下我应该考虑 8 个连通性吗？
不，连接可以用两种方式定义:4 个连接和 8 个连接，并且没有默认的连接定义。此外，面试问题大多比较低调，因此您必须向面试官澄清，以免出现歧义。
找到包含全黑色的最小矩形。
您可以用 -Infinity 替换所有的，然后使用 Kadane 的二维数组算法找到总和最大的子矩形。在应用 kadane 之前，您还必须将零替换为 1。对于实现see this .
注意，无论黑色是否全部相连，寻找全0的最大子矩形的算法都是一样的。
关于algorithm - 通常对连通性使用什么定义，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22599998/