复杂度为 O(n) 的二维数组中的寻峰算法
Peak finding algorithm in 2d-array with complexity O(n)
问题如题。
我想弄清楚是否有一种方法可以找到峰值元素
O(n) 时间内的二维数组，其中 n 是二维数组中每条边的长度，即
n^2 个元素。
根据定义，二维数组中的 "peak" 是这样的元素 >=
到它的所有邻居（即上、下、左和右插槽中的元素）。
我在以下位置阅读了课程笔记：
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
并理解如何在 O(nlogn) 中做，但似乎不太
掌握如何做 O(n).
谁能想出或解释一下如何在 O(n) 中解决这个问题？
编辑：n 是数组每一边的长度，即总共有 n^2 个元素。
链接的 PDF 中给出的第二种算法是 O(n)。 A "window" 定义为当前子方块的边界（即所有四个外边）、中间列和中间行。以下是该算法的摘要：
- 在当前中找到最大值window
- Return如果它是一个峰值
- 否则，找到这个最大值的较大邻居，并在相应的象限中递归。
如幻灯片中所述，时间复杂度定义为 T(n) = T(n/2) + cn（T (n/2)项是由于边长在每次递归时减半；cn项是在当前求最大值所需要的时间window)。因此，复杂度为 O(n)。
此算法的正确性基于其中一张幻灯片上列出的几个观察结果：
If you enter a quadrant, it contains a peak of the overall array
这基本上是同一一维论证的概括。只有当象限包含的元素大于边界上的所有元素时，您才进入象限。因此，要么该元素将成为峰值，要么您可以保持 "climbing up" 直到在象限中的某处找到峰值。
Maximum element of window never decreases as we descend in recursion
递归中的下一个window总是包含当前window的最大元素，所以这是真的。
Peak in visited quadrant is also peak in overall array
这是根据峰值的定义得出的，因为它仅取决于直接邻居。
问题如题。 我想弄清楚是否有一种方法可以找到峰值元素 O(n) 时间内的二维数组，其中 n 是二维数组中每条边的长度，即 n^2 个元素。
根据定义，二维数组中的 "peak" 是这样的元素 >= 到它的所有邻居（即上、下、左和右插槽中的元素）。
我在以下位置阅读了课程笔记： http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf 并理解如何在 O(nlogn) 中做，但似乎不太 掌握如何做 O(n).
谁能想出或解释一下如何在 O(n) 中解决这个问题？
编辑：n 是数组每一边的长度，即总共有 n^2 个元素。
链接的 PDF 中给出的第二种算法是 O(n)。 A "window" 定义为当前子方块的边界（即所有四个外边）、中间列和中间行。以下是该算法的摘要：
- 在当前中找到最大值window
- Return如果它是一个峰值
- 否则，找到这个最大值的较大邻居，并在相应的象限中递归。
如幻灯片中所述，时间复杂度定义为 T(n) = T(n/2) + cn（T (n/2)项是由于边长在每次递归时减半；cn项是在当前求最大值所需要的时间window)。因此，复杂度为 O(n)。
此算法的正确性基于其中一张幻灯片上列出的几个观察结果：
If you enter a quadrant, it contains a peak of the overall array
这基本上是同一一维论证的概括。只有当象限包含的元素大于边界上的所有元素时，您才进入象限。因此，要么该元素将成为峰值，要么您可以保持 "climbing up" 直到在象限中的某处找到峰值。
Maximum element of window never decreases as we descend in recursion
递归中的下一个window总是包含当前window的最大元素，所以这是真的。
Peak in visited quadrant is also peak in overall array
这是根据峰值的定义得出的，因为它仅取决于直接邻居。