在二维数组中寻找局部最大值

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)的复杂度。尽管我的朋友坚称应该存在一个渐进更好的算法，但我认为你不能做得比这更好。有任何提示吗？

我考虑了分治的思路，但我感觉不可能在不遍历所有数字的情况下检测到所有局部最大值，这必然是O(n^2)的复杂度。我是对还是忽略了什么？

- arya

---

如果你只想要一个局部最大值，它可以在少于n^2的时间内找到。 - Yu-Han Lyu

@Habisoft 给出了最佳答案。 - Naresh Joshi

请注意，这里对于局部最大值的描述是有缺陷的。需要增加一个要求，即如果相邻的元素相等，则它们也必须是局部最大值。也就是说，需要递归地扫描相等的相邻元素，以验证它们中没有任何一个具有更大的相邻元素。 - Cris Luengo

Answer 1

提醒一下，一个二维网格的局部最大值或最小值可以使用分治策略在O(nlgn)的时间内计算出来。这比包含在时间复杂度为O(n^2)类中的暴力算法稍微好些。此外，可以改进分治算法以获得用于二维网格极值查找的O(n)算法。

查看一下有关这种峰值挑选算法背后理论的笔记（我相信还有更多其他资料）：

http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

- HabiSoft

---

你的解决方案并不能找到所有的局部最大值，只能找到一个局部最大值。考虑一个矩阵 I * J，其中每个单元格都只包含值 5，在这种情况下，你需要访问每个 I * J 的单元格，以确保矩阵中没有出现 4 或 6 的情况。 - Seph

最好的方法是选择这种方式。 - Naresh Joshi

@HabiSoft，您的解决方案似乎很好，并且可以在O（log n）的时间复杂度内解决1D数组问题，您能否也发布二维矩阵中寻找局部最大值的伪代码？我只是通过阅读内容无法理解。 - Naresh Joshi

2D算法的解释在提供的链接中给出。如果我没记错的话，它可能只是将1D算法应用于nxn矩阵的所有列上，这意味着将O(log n)算法应用n次，从而得到O(n log n)算法。 - HabiSoft

问题要求“找到所有局部最大值”，而不是“找到一个局部最大值”。在一维中，可能有n/2个局部最大值，因此无法在O(log n)时间内找到它们全部。 - Cris Luengo

Answer 2

除非你的数组是方阵，否则你的解决方案实际上是 O(I * J) 而不是 O( n^2 )。严格来说，在你的二维数组中只有 N 个元素，因此这个解决方案是 O(N)。唯一能使它成为 O( n^2 ) 的方法是如果数组是方阵，如 I = J = N。

由于比较的是 <= 而不是 <，你仍然需要检查下一个元素，任何快捷方式都可能是特定于处理器的。

最坏情况是整个数组都是局部最大值，因为整个数组等于相同的值。

因此，您必须访问每个元素一次，使其成为 O(N)。

为了提高这种情况下的实际性能，您需要使用指针来访问数组，因为在大多数语言中，二维数组的性能要比一维数组差得多。

- Seph

Answer 3

我相信这个问题可以用所谓的对手论证来回答，它可以给出比较次数的下限。

而且在我的观点中，你是正确的... 这至少需要n^2次比较。

- vidit

---

@kasavbere- 我的意思是至少n^2.. 我们在谈论下限。 - vidit

Answer 4

给你一个大小为4 x 4的数组。你需要完成以下任务：

1. 使用rand()函数填充数组中的一些随机数。

2. 对于每个单元格(i,j)，你需要找到该单元格所有可能邻居中最大的数字。

3. 然后将该最大数字放入该单元格(i,j)中。

示例输入：

177 -90 12 7
1 34 43 67
11 11 122 45
6 90 98 93

样例输出：

34 177 67 67
177 177 122 122
90 122 98 122
90 98 122 122

- sajib

Answer 5

我非常确定这个问题无法在少于O(n^2)次比较中解决。假设一个棋盘的二维矩阵，其中所有白色方块为1，黑色方块为0。它将有O(n^2)个解决方案，每个解决方案至少需要一次比较。

- ElKamina

---

谢谢，你的例子真的很好地阐明了一切 :) - arya

正如我的回答所提到的，由于该数组没有被声明为“方阵”，因此它实际上只是 O(n)，其中 n 是元素的总数，即 n = i * j。如果我是面试官，我会寻找这种理解。 - Seph

@arya 这个答案是不正确的。请考虑我提供的回复。 - kasavbere

@kasavbere，(n-1)*(n-1) 仍然是 O(n^2) 哦，爱因斯坦！ - ElKamina

@ElKamina，(n-1)(n-1)不是我发帖说的内容。你读了我的帖子吗？(I-2)(J-2)只是优化的起点。另外，你的帖子中说：“它将会有O(n^2)个解决方案，并且每个解决方案都需要至少一次比较。”这是一个错误的观察。 - kasavbere

Answer 6

以上的答案只是捍卫了一个数学模型。 这个模型来自于对问题的简单看法。

如果你从事编程工作，你应该知道处理器能做什么。 你应该意识到代码在一个线程中运行。 你应该想知道一个任务是否可以分成更小的任务，这样你就能够进行多线程处理，并接近1/总线程执行速度提升。

实现这一点的代码取决于语言，所以我不在这里提供示例。

但你必须记住，如果你处理的是白噪声或棋盘等值，那么所有的值都应该被处理，因此没有逃避快速解决问题的方法。只有当你的数据不同，比如气压数据或在随机放置的飞镖板上找到靶心时，你才能创建算法，不需要检查每个值（找到梯度问题），或使用统计分析。

- Peter

Answer 7

无需访问每个元素：

你只需要想象出网格，就会发现这可以在比平方时间复杂度n^2（或I*J）少得多的时间内解决。以下是优化方法，按层次列举：

1] 对于一个I * J矩阵，你只需要搜索(I-2)*(J-2)个元素。为什么？因为边界由于未定义的元素无法成为最大值：

 e.g. grid[0][J] or grid[I][0] could never be maxima. because of the -1 neighbor.

因此，对于一个10乘12的网格，我们不需要访问所有的120个元素，而只需要查看80个元素。

2] 如果grid[I][J]是最大值，那么我们可以跳过所有相邻的[I][J]单元格，继续搜索。这将进一步减少要比较的元素数量。

因此，答案是否定的，你不必访问每个元素。

- kasavbere

---

虽然您的优化是正确的，但是算法仍将是O(i*j)。首先，通过消除边框来减少检查次数对于相对较小的网格有效（10x12为33％），但对于较大的网格几乎没有帮助。在100x120的网格上，您会从12000个正方形减少到11564个，这小于4％。您的第二个优化实际上在不存在局部极大值的情况下不起任何作用。 - dlev

这是正确的。这里的重点是，作为结论基础的前提条件和证据与结论本身同样重要。仅仅通过不真实的论点得出正确的结论是不够好的。 - kasavbere

另一个人确实说过：“它将具有O(n^2)的解决方案，每个解决方案都需要至少一次比较。”我也认为严谨性很重要。 - tribal

正如我在回答中所提到的，你的第二点2]是不正确的，因为测试条件是<=，也就是说，如果整个矩阵的值都相同，那么每个单元格都是最大值。 - Seph

在数学中，当你计算给定域上的局部最大值时，边界上的点通常可以被视为局部最大值。例如，我会说函数 f(x) = x 在域 [0,1] 上具有局部最大值 x = 1，因为在该点，函数的值比域内任何其他相邻点的值都要大。同样，我会说 1 x 2 数组 [4 5] 在 5 处具有局部最大值。然而，我同意发布的规格说明对于如何处理边界的方式相当不清楚。 - Alderath