在2D阵列中查找局部最大值

Question

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]

我被要求找到给定2D阵列中的所有局部最大值.

执行此操作的简单方法是遍历所有元素,并检查每个元素是否是局部最大值.这将是O(n ^ 2).虽然我的朋友坚持认为应该存在一个渐近更好的算法,但我觉得你做不到这一点.任何提示？

我正在思考Divide and Conquer的思路,但我觉得如果不经过所有数字就不可能检测出所有的局部最大值,这些数字必然是O(n ^ 2).我是对的还是我错过了什么？

Answer 1

只需要抬头,2D网格的局部最大值或最小值可以使用分而治之策略在O(nlgn)时间内计算.这比O(n ^ 2)时间复杂度类中包含的强力算法稍微好一点.此外,可以对分而治之算法进行改进,以获得用于2D网格极值发现的O(n)算法.

查看这些峰值拣选算法背后的理论说明(我确信它们的材料更多):

您的解决方案找不到所有局部最大值,只找到局部最大值.考虑一个矩阵I*J仅在每个单元格中包含值5,您将需要访问每个所有I*J单元格以确保矩阵中某处没有4或6. (3认同)

Answer 2

我很确定这不能通过少于 O(n^2) 的比较来解决。假设棋盘二维矩阵，其中所有白色方格都是 1，黑色方格都是 0。它将有 O(n^2) 个解，每个解至少需要一次比较。