在 O(n) 时间内找到 n x n 矩阵中的局部最小值

所以，这不是我的家庭作业问题，而是取自 coursera 算法和数据结构课程的未评分作业（现已完成）。

You are given an n by n grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n² numbers in the input, you cannot afford to look at all of them. Hint: Think about what types of recurrences would give you the desired upper bound.)

Since the numbers are not in any order, I don't see how we can get away with any thing but O(n²) comparisons.

我们可以通过看看 Jared 的答案是如何出错的来调整 Words Like Jared 的答案。

这个答案的想法是一个很好的答案，那就是“滚下山”。这只是意味着，如果您在一个元素上，请检查它是否是局部最小值。如果是这样，你就完成了；否则，步长至其最近邻居中最小的一个。最终这必须终止，因为每一步都是到一个较小的元素，并且不能在有限数组中永远持续下去。

这种方法的问题在于“滚动”可能会到处蜿蜒：

20 100 12  11 10 100  2
19 100 13 100  9 100  3
18 100 14 100  8 100  4
17  16 15 100  7   6  5

如果从左上角开始并“滚下山”，您将访问数组中大约一半的元素。这太多了，所以我们必须限制一下。

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

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

现在考虑一下如果你从那里“滚下山”会发生什么。显然，您最终会达到局部最小值。 （我们实际上不会这样做，因为这会花费太长时间。）But，在滚动的过程中，你永远不会离开那个象限...因为要做到这一点，你必须穿过中间列或中间行，并且这些元素都不会小于你开始的位置。因此，该象限在某处包含局部最小值。

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

该算法需要时间 2n + 2n/2 + 2n/4 + ...，等于 4n，即 O(n)，所以我们就完成了。

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

[Update]

As Incasator指出 https://stackoverflow.com/a/24461101/768469，这个答案并不完全正确，因为在你“递归”之后，你可能会再次滚出象限......

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