二维网格问题的算法？

Question

老实说，这是一道作业题，但我就是找不到答案。请记住，我不是在寻求答案，而只是寻求一些指导。

问题: 设计一个在 O(n) 时间(线性)内运行的算法，该算法可以在 2D 网格上定位单个可疑房屋(点)。如果它的耗电量等于或大于其两个垂直和两个水平邻居的耗电量，则值得怀疑。注:只想退还一间可疑房屋

解决方法: 甚至不确定如何实现这样的解决方案。如果您检查 n 个房屋，您还可以检查其周围的四个邻居。 4n/n^2 简化为 4/n。这意味着随着网格的扩大，它不太可能找到可疑的房子。

我尝试过的: - 不同的数据结构(大多数是nlogn) - 折叠网格(再次nlogn)

提前致谢。

编辑:

我的错误，网格是 (n x n) 使得房子的数量为 n^2，很抱歉造成混淆。

编辑2:

正是这个问题，也许我读错了？

警察正在寻找有特别大电的房子- 三联消费。为了简化问题，假设他们是 调查布置在 n×n 网格上的房屋。每个房子在 电网有一些电力消耗，e(i, j)。警方考虑 如果房子的耗电量等于或大于 比它的每个垂直和水平邻居。设计算法 在 O(n) 时间内运行并返回可疑房屋的位置。

Answer 1

您基本上是在寻找用电量达到本地最大值的房子。您可以通过从任意一所房子开始，然后走到相邻的房子(如果它的用电量更高)来找到其中之一(重复直到没有相邻的房子更高)。

这将在 n x n 网格上花费 O(n) 时间。

编辑:评论者是对的，在最坏的情况下这可能需要 O(n^2) 时间。