在二维数组中找到局部最小值

Question

给定一个 $N\times N$ 的由 $N^2$ 个不同整数组成的数组 $a$，设计一个 $O(N)$ 算法来寻找一个局部最小值：一对索引 $i$ 和 $j$，使得：

- $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][j-1]$

我在一个在线算法书籍 Java编程导论, 第4.2章 排序与查找 中找到了这个问题。

它类似于第35题（同一页）：

给定一个由 $N$ 个实数组成的数组，编写一个静态方法在对数时间内找到一个局部最小值（一个索引 $i$，使得 $a[i-1]

它有一种基于二分查找的解决方案，但我无法找到。

- learner

---

anuja: 一维情况下的对数时间：询问A[N/2]。如果它比A[1]大，那么你在前半部分有一个局部最小值。如果它比A[n]大，那么你在后半部分有一个局部最小值。否则，如果A[N/2]<A[N/2-1],A[N/2+1]，你在N/2处有一个局部最小值。否则，如果A[N/2]>A[N/2+1]，你在后半部分有一个局部最小值，而对于A[N/2]>A[N/2+1]，你在前半部分有一个局部最小值。画图以确信... - sdcvvc

为了帮助理解问题35的解决方案（以及可能是这个问题），请注意您不是在寻找最小值，而是在寻找局部最小值。 - Lasse V. Karlsen

问题陈述有误（请参见我的答案）。边缘单元格未定义。如果边缘单元格不能是局部最小值，则没有解决方案。如果边缘单元格可以是局部最小值，则可以使用分治解决方案。 - Andrew Tomazos

Answer 1

同样的问题在网页版书籍《算法》(Robert Sedgewick和Kevin Wayne著)的“创造性问题”章节，问题19中提到。

作者在该链接中给出的问题提示是：

在第N/2行找到最小值，在列中检查相邻的p和q，如果p或q更小，则在该半部分中递归。

一种更好的方法是： 在第N/2行找到最小值，在其列中检查所有条目，如果我们在列中获得较小的条目，则在较小列条目所属的行中递归。

例如， 对于下面的数组，N=5:

1  12  3   1  -23  
7   9  8   5   6
4   5  6  -1  77
7   0  35 -2  -4
6  83  1   7  -6

步骤1：中间行是[4 5 6 -1 77]，即第3行。

步骤2：当前行中最小的条目是-1。

步骤3：最小条目（即-1）的列邻居是5和-2。其中-2是最小的邻居。它在第4行。

重复步骤2-3，直到获得局部最小值。

编辑：

例如，@anuja评论中提到的问题如下： （主要问题是针对n x n数组。此输入为3 x 4数组，但我们可以使用它）：

1 2 3  4 
5 1 6 -1
7 3 4 -2

步骤1：中间行是[5 1 6 -1]，即第2行。

步骤2：当前行中的最小输入为-1。

第三步：最小值（即-1）的列邻居是4和-2。 -2是最小的列邻居。它在第三行。

迭代到第二步：-2是其行中最小的，并且是其列邻居中最小的。因此，我们以-2作为局部最小值的输出。

- Tejas Patil

---

在最坏的情况下，时间复杂度为n^2。考虑一个由倒序排列的数字组成的数组，每一行之间由一堵比其更高的数字组成的墙隔开。你需要循环n*(n/2)/2次才能追踪链条到达它的末尾。我认为，如果我们在第二步后添加一个步骤，在包含较低值的列上重复1、2，然后继续进行2、3循环，则时间复杂度为O(n)。 - Loren Pechtel

这个算法看起来比较可爱，但并不是O(n)。在一行中找到最小值的时间复杂度是O(n)。 我们需要查找行最小值的次数可能取决于n（对于某些矩阵模式）。 可以构建一个矩阵，强制该算法访问所有行和列。考虑以下行为 8 3 4 8、8 8 8 7、8 8 5 6 和 1 2 8 8 的矩阵。你的算法将访问所有行和所有列，使其成为一个O(n^2)算法。（因此，对于这个输入矩阵，只需循环遍历所有元素并找到整个矩阵中的最小元素将更有效）。 - Alderath

你的回答很令人困惑，因为第一种方法不是坏的，但是错误的。我花了三个多小时的时间才找出为什么它不起作用。有一些边界情况，你必须采取你所说的“更好的方法”。以下是一个例子，其中采用中间行/列的方法不起作用（N=5）：10, 8, 9, 12, 11 9, 7, 8, 9, 0 10, 6, 9, 6, 1 12, 5, 4, 3, 2 13, 9, 7, 8, 10（在我的练习中只有一个全局最小值）。对于这个例子，算法会陷入左上角（因为有 7, 8, 9...）。 - Chaoste

@D.W. 但是如果我们想要满足 OP 给出的所有条件，那么在这种情况下上述方法将行不通，对吗？如果我们考虑以下例子：{4, 3, 1, 14, 16 }, {10, 12, 5, 7, 8 }, {4, 6, 7, 4, 8 }, {10, 8, 12, 14, 10 }, {5, 10, 12, 5, 10} 那么按照上面给出的方法，答案将是在位置 (2,0) 的 4。但是如果我们想要满足所有条件，那么真正的答案是在位置 (2,3) 的 5。 我有什么逻辑错误吗？ - AshwinK

@AshwinK，是的，你漏掉了一些东西。有多个有效答案。在位置（2,0）处的4是一个有效答案。在位置（4,3）处的5也是一个有效答案。这两个都满足问题中的所有要求。 - D.W.

Answer 2

更新：假设边缘不是局部最小值，因为在原始问题陈述的四个比较中没有将其定义为这样。在这种情况下，此答案是正确的（不可能）。如果重新定义问题，则边缘可以是局部最小值，那么每个矩阵都至少包含一个局部最小值-因此您可以使用分而治之的方法。

如果边缘单元格不能是局部最小值：

按照陈述的方式，问题无解。读取N*N的数组元素需要O(N^2)时间。由于矩阵中可能存在单个“隐藏”的局部最小值，因此必须进行证明。

如果您的意思是要求O(N^2)算法，则简单遍历每个元素并将其与其4个邻居进行比较需要O(N^2)时间。

要么您记错了面试问题（实际还有其他内容），要么这只是一个微不足道的编码练习。

证明：

1. Construct a NxN matrix such that each cell has the value M[i,j] = N*i + j.
2. Select a random x,y (1 < x < N and 1 < y < N) and assign M[x,y] = -1

这个矩阵恰好有一个局部最小值点(M[x,y])，该位置与其他单元格中的值无关，因此其他单元格不提供有关其位置的任何信息，因此不可能有任何系统可以搜索它，期望的比(O(N^2)更好的单元格搜索次数为(N^2/2))。

换句话说，你可能会在一个几乎所有单元格都是零的矩阵M[i,j] = 0中进行搜索，除了M[x,y]=-1的最小值点。

这个证明取决于能够在步骤1中构造没有局部最小值点的矩阵。如果边缘单元格可能成为局部最小值点，则每个矩阵都必须有一个，因此这个证明不再成立。

- Andrew Tomazos

Answer 3

访问一个随机单元格。如果它的四个邻居中有任何一个值更小：则去那个单元格。如果邻居都比自己大，那么你就处于局部最小值。如果单元格具有相等的值，则避免循环会有一些困难。

更新：

我们可以选择最小的邻居，而不是只访问一个邻居。

最困难的拓扑结构似乎是两个“同心螺旋”，其中一个作为螺旋堤坝。在最坏的情况下，这种情况仍然需要大约N/2步（其中N为单元格数）。

- wildplasser

---

一般来说，这是不可行的（你可以创建一个“螺旋”，强制访问O(N^2)个单元格）。 - sdcvvc

这并不算太糟糕。但它的真正缺陷在于，你不能保证有任何局部最小值存在。或者说，任何存在的局部最小值都可能无法被距离其两个或更多单元格的“局部”过程找到。 - RBarryYoung

@sdcvvc 你能给一个螺旋的具体例子吗？ - fgb

如果不是从随机单元格开始，而是从中间行的最小值开始呢？ - fgb

@wildplasser: 你可能不需要访问它们所有，但如果你从一个很长的路径的起点开始，你最终会访问n*(n/2)个单元。请注意，路径还可以是交错的。 - Loren Pechtel