相关疑难解决方法(0)

我在做这从MIT算法课程.在第一堂课中,教授提出了以下问题: -

2D阵列中的峰值是使得它的4个邻居都小于或等于它的值,即.对于

a[i][j] 成为当地最大值,

a[i+1][j] <= a[i][j] 
&& a[i-1][j] <= a[i][j]
&& a[i][j+1] <= a[i][j]
&& a[i+1][j-1] <= a[i][j]

现在给定一个NxN 2D阵列,在阵列中找到一个峰值.

O(N^2)通过迭代所有元素并返回峰值,可以很容易地及时解决这个问题.

然而,它可以优化要解决O(NlogN)通过使用分而治之的解决方案为解释时间在这里.

但是他们说有一种O(N)时间算法可以解决这个问题.请建议我们如何及时解决这个问题O(N).

PS(对于那些了解python的人)课程工作人员在这里解释了一种方法(问题1-5.峰值证明),并在他们的问题集中提供了一些python代码.但解释的方法完全不明显,很难破译.python代码同样令人困惑.所以我已经为那些了解python的人复制了下面代码的主要部分,并且可以从代码中分辨出正在使用的算法.

def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    subproblems = []
    divider = []

    if rowSplit:
        # the recursive subproblem …