在O（n）时间中找到nxn矩阵中的局部最小值

在O（n）时间中找到nxn矩阵中的局部最小值

通过查看它可能出错的方式，我们可以像贾里德的答案那样改编单词。

答案中的一个主意是“滚下坡路”，这是一个好主意。这只是意味着，如果您在元素上，请检查它是否是局部最小值。如果是这样，那么您就完成了；否则，请移至与其最近的邻居中的最小邻居。最终，这必须终止，因为每一步都是针对较小的元素，并且不能永远在有限的数组中进行。

这种方法的问题在于，“滚动”会在各处蔓延：

20 100 12  11 10 100  219 100 13 100  9 100  318 100 14 100  8 100  417  16 15 100  7   6  5

如果从左上方开始并“下坡”，您将访问数组中大约一半的元素。太多了，因此我们必须对其加以限制。

首先检查中间列和中间行。在所有这些元素中找到最小的元素，然后从那里开始。

从那里“下坡”滚动一步，进入四个象限之一。您将输入一个象限，因为中间列和/或行中的相邻元素较大，因此，两个相邻象限中只有一个是“下坡”的。

现在考虑如果您从那里“下坡”会发生什么。显然，您最终将达到本地最低要求。（我们实际上不会这样做，因为它会花费太长时间。） 但是
，在滚动过程中，您永远不会离开该象限…因为这样做，您将不得不越过中间列或中间行，这些元素都不比您开始的地方小。因此，该象限在某处包含局部最小值。

因此，在线性时间内，我们确定了必须包含局部最小值的象限，并且将n切成两半。现在只需递归即可。

该算法需要2n + 2n / 2 + 2n / 4 + …的时间，等于4n，即O（n），所以我们完成了。

有趣的是，除了关键部分外，我们根本没有使用“向下滚动”：证明算法有效。

[更新]

正如Incassator指出的那样，这个答案并不完全正确，因为在您“递归”之后，您可能会再次退出象限…

最简单的解决方法是在“下坡”之前找到中间行，中间列 和边界 中的最小元素。