在遍歷的2D網格中查找峯值

Question

我們有一個n-n網格，左下角的座標爲（0,0），右上角爲（n，n）。網格中的單元格都有不同的值，我們的目標是找到一個局部峯值，它被定義爲一個值大於其左，右，上，下相鄰值的單元格（即，對角線相鄰的單元格不物）。

事情是，我們只能通過訪問該單元格來查看單元格的值（即，如果不先（i + j）步驟從（i + j） 0,0））。我們如何在O（n）步驟中找到局部峯值？

Answer 1

它可以使用分治策略在O（nlgn）時間內計算。這比O（n^2）時間複雜度類中包含的蠻力算法稍微好一些。

我在google上找到了這個pdf。希望它會有所幫助。

Local maxima using Divide and Conquer