给定一个整数M的矩阵，峰值是一个数组的元素，且不小于其4个相邻元素（上，下，左，右）。有一种很好的线性时间算法（用于n×n矩阵的O（n））来找到一个峰值，例如在这些讲义中，或者在该代码中， O（n log n）时间解决方案稍微简单一些。
假设我想找到k个峰（如果有那么多）。有没有办法在O（n + k）或O（n log n + k）时间内做到这一点？
答案是不。如果那样的k > 1话，最差的表现将是O(n^2)。
问题在于“如果存在的话”部分。当输入包含少于k峰值的峰时，仅当我们确定k要查找的峰少于峰时，我们的算法才能终止。我将在下面证明，k如果我们O(n^2)在相邻元素之间进行了比较，则只能确定峰数少于峰值。
证明：
要确定某个元素不是峰值，我们必须将其与至少一个相邻元素进行比较-如果该相邻元素碰巧更大，则该元素不是峰值。如果我们还没有将一个元素与其相邻元素进行比较，那么它可能仍然是一个峰，并且我们所做的每个比较都将一个元素中的一个排除为峰。知道k输入中的峰值少于等于知道至少有n^2 - k + 1非峰值，这要求我们至少n^2 - k + 1进行了比较，即O(n^2)。由于k > 1存在带有< k峰值的输入，因此在最坏的情况下，我们将必须执行这些O(n^2)比较，然后再停止搜索。
注意事项：
在这种情况下不会出现此问题的原因k = 1是，确保每个输入至少具有一个峰值。当我们找到第一个峰时，我们便停止了搜索，因此我们不必检查是否有其他峰可以找到。
我怀疑我错过了一些东西，因为“是”的答案对我来说似乎是显而易见的。使用给定的算法找到峰值，但找到后不要停止。相反，原路返回；继续寻找，直到找到k峰值，或者用尽分治算法。
在某些病态情况下（例如导致已知峰值的多个起点），您可以通过安排搜索顺序来提高性能。当您沿着树原路返回然后跨过宽度移动时，不要移动到相邻位置。相反，移动到最远的未搜索节点。您可以使用O(1)距离函数找到它，或者简单地获取一个足够远的距离函数，给定搜索树的级别（子矩阵大小的良好估计）。
我的想法是在研究一个包含k不同峰值的矩阵，但用这种方法不能很好地解决问题。二维迷宫设计的连通性提供了很多好的工具——这相当于从给定的起点找到一条迷宫路径。