在一个NxN的矩阵中找到所有的峰值

Question

我正在尝试使用直接方法创建一个算法，以查找 N x N 矩阵中的所有峰值。但是我遇到了一些问题，例如处理角落、第一行和最后一行以及第一列和最后一列。我将问题描述如下：

[ ][c][ ][ ] a is considered a 2d peak
[d][a][e][ ] or a hill iff a >= b,
[ ][b][ ][ ] a >= d, a >=c, a >=e
[ ][ ][ ][ ]

然而，在我需要将角落表示为下面的样子时，c和d不存在。我必须评估太多的条件才能得到更通用的内容。例如，对于下面的a，我需要检查位置a是否有效，如果row-1 < 0，则我就不需要检查a上方的任何东西；如果col-1< 0，则左侧的任何内容都不需要检查。

[a][e][ ][ ] 
[b][ ][ ][ ] 
[ ][ ][ ][ ] 
[ ][ ][ ][ ]

但是如果我们将位置a移到其他角落，甚至评估其他位置，例如上面的e，我需要确保e处于一个有效的位置，其中row-1存在，以防止评估该位置并获取错误（在上面的例子中，如果检查e >= row-1中的元素，我肯定会出错）。我已经实现了一段考虑到角落、第0行和第n行以及第0列和第n列的代码，但是我停下来开始思考如何使它更易读和简单。

void find_hill(){
    int i, j;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            //check corners
            if(i-1 < 0){
                if(j-1 < 0){
                   //check if arr[i][j] >= arr at i,j+1 and i+1,j
                }
                if(j+1 > n-1){
                   //check if arr[i][j] >= arr at i,j-1 and i+1,j 
                }
            }                
        }
    }     
}

我想讨论如何在这里得出解决方案。我应该从哪里开始，以获得简单的东西？我想到了一种类似于洪水填充的方法，但它会分别填充每个位置，可能行不通，因为我最终会遇到相同的问题！

- Kennet Emerson

---

你可以编写一个函数 get(i, j, n)，如果 i 和 j 是有效的，它将返回 arr[i][j]，否则返回 INT_MIN。 - M Oehm

@MOehm 对的，但是这如何解决我需要检查i-1、j-1、i+1和j+1而不为角落和顶部、底部和侧面制作太多表达式的问题，以至于它们没有邻居？ - Kennet Emerson

通过将条件检查移入函数中，您可以在客户端代码中无条件地探测所有四个方向。通过将默认值设置为INT_MIN，您确保峰值测试将在边缘和角落找到峰值。但是，您仍然需要明确检查所有四个邻居。 - M Oehm

请看这里，了解我所说的内容。（点击此处查看）这两个答案采用了类似的方法，避免了区分角落和边缘情况。 - M Oehm

很抱歉我没有恰当地解释 INT_MIN。 （它不是 int 的最小大小，而是其最小可能值。这些和类似的常量在 <limits.h> 中定义。）我本可以说“一个小值，您知道它比矩阵中的所有其他值都要小”。如果您的所有值都是正数，则该值可以为0。 - M Oehm

Answer 1

我建议采用以下技巧：在首行、末行、首列和末列上分别复制一份内容，如下所示：

[ ][a][b][c][ ]
[a][a][b][c][c]
[d][d][e][f][f]
[g][g][h][i][i]
[ ][g][h][i][ ]

那就将循环从1开始，到n-1结束。

- Matthieu Latapy

---

根据你解决问题的实际情境，这是完全可以接受的。编程，像大多数艺术一样，是关于在各种价值之间达到和谐。除非你只是挑战自己，如果在实际情境中你有可用的千兆字节RAM，你应该编写可读性好、易维护等代码，而不是那些从不浪费CPU周期或RAM字节的代码。后一种行为被称为过早优化。这不仅浪费你的努力，而且从长远来看实际上会产生相反的效果。@KennetEmerson - szpanczyk

@KennetEmerson...这将证明对性能至关重要，但很可能会破坏该代码与其余部分的交互方式，并产生连锁反应。但这意味着你应该从一开始就选择适合你所计算的正确的抽象模型、通信方式、技术、库等等。如果你从一开始就知道某些计算会很费力，你应该从一开始就选择完美的算法，并在提交时设计它周围的环境，而不是相反。当然，但是... - szpanczyk

在确定有需求之前，应避免所有你可以未来很容易完成的优化。如果您知道如何正确编写代码，您将知道从一开始就需要做出哪些决策以及什么可以先快速编写并根据需要进行扩展。这是其中一个要点 - 虽然您的代码应该从一开始就“干净”，但尽量避免写入比严格必要的更多代码。如果您需要为性能优化“放弃”它，那么它会感觉像是删除占位符。您实际上没有承担任何成本。 - szpanczyk

另一件事情是，你过早地进行了优化，然后发现你花费了很多时间打磨的代码并不完全适合实际场景，结果影响了性能的核心...现在需要完全重写，因为虽然它在执行任务方面非常出色，但它的目标略有偏差，如果这段代码在客户机上每秒被调用一百万次，那么它必须是你公司能够想到的最好的。 如果只是几行代码可以工作，那么就没有必要为放弃它而流泪了。 - szpanczyk

@szpanczyk，你告诉我的一些东西我已经很熟悉了，但还有其他的我不太清楚。非常感谢你的教导：）。此外，在这里回答问题时，我会更多地考虑理论性的答案。 - Kennet Emerson

Answer 2

在算法范围内，有几种选择。

您可以增加矩阵的大小。在理论层面上，这是一个完全可接受的选项，因为它只会按比例增加矩阵的宽度而增加内存和计算量。但实际上，如果您正在处理相对较小的矩阵，它可能会将其大小增加多达9倍（例如1x1矩阵增加到3x3）。如果您认为这不够优雅，那么您可能会发现很多事情都不够优雅，而避免这种不够优雅的“解决方案”通常比这些事情更加不优雅和麻烦。

另一种选择显然是循环中的条件语句。从理论上讲，它非常完美，因为它根本不会增加内存，并且仅向您已经执行的每个循环周期添加一个常数... 实际上，它确实会使每个周期花费额外的时间来检查条件，因此无论您处理大量的小矩阵还是较少但更大的矩阵，都会使代码性能变差。如果该代码很可能成为瓶颈或导致许多性能问题的生成器，则这实际上是最差的选择。如果不太可能出现这种情况，则选择这个选项是一个不错的选择，因为它以明确简洁的方式显示您的意图。因此，是否是最佳选择取决于上下文，并且如果它是其他程序员想要快速阅读的代码部分，或者是性能应用程序中最负责的部分，则使用或不使用此解决方案可能会引起他们的愤怒。

最后，您可以只为所有特殊情况编写单独的代码 - 分别检查四个角、四个边和矩阵的其余部分。这不会导致“不必要”的内存使用，并将导致最快的工作代码。但与其他两个选项相比，它看起来很难读。

话虽如此，我在这里没有涉及软件工程方面。您可以使用各种技术使每个选项看起来更好、更易读和/或可维护，例如创建一个get（x，y）函数来验证其输入 - “循环中的条件”场景的变体，这已经在另一个答案中提到过。

- szpanczyk

---

明白了你的意思。我认为你是正确的。考虑到你之前提到过过早优化可能会适得其反，我们可能会忽略一些简单的解决方案，比如复制第一行和最后一行以及列。也许在听完你的话后，我会更倾向于思考简单的解决方案而不是针对未来问题进行优化。感谢你的贡献。 - Kennet Emerson

Answer 3

这类似于将内核应用于图像，例如Sobel滤波器或其他使用滑动窗口方法的滤波器。通常，我会忽略边界，但是如果您想要在矩阵边界上检测山丘，则需要识别窗口类型。

如果您不关心内存复制，可以在嵌套循环中创建一个3x3的窗口，并且如果该窗口位于角落处，则使用中心值填充相应的值。也许像这样：

int window[3][3];

for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
    {
        window[1][1] = arr[i][j];
        window[0][1] = (i - 1 < 0) ? window[1][1] : arr[i-1][j];
        window[2][1] = (i == n - 1) ? window[1][1] : arr[i+1][j];

        window[1][0] = (j - 1 < 0) ? window[1][1] : arr[i][j-1];
        window[1][2] = (j == n - 1) ? window[1][1] : arr[i][j+1];

        // Process window
        // ...
    }
}

- dodooft

Answer 4

void find_hill() {

    int i, j, k, l;
    
    for(i = 0; i < n; i++){
    
        for(j = 0; j < n; j++){
        
            for(k = i-1; k <= i+1; k++) {
                
                for(l = j-1; l <= j+1; l++) {
                    
                    if( k > 0 && k < n && l > 0 && l < n && (i-k)*(j-l) == 0 && arr[i][j] >= arr[k][l] ) {
                        
                        arr[i][j] is a peak;
                    }
                }
            }                
        }
    }     
}

你也可以使用这个条件

if( !(k == i && j == l) && k > 0 && k < n && l > 0 && l < n && (i-k)*(j-l) == 0 && arr[i][j] > arr[k][l] )

使用!(k == i && j == l)可以防止您在9次中运行条件的其余部分1次，但会增加它本身在9次中运行的权重。

在这9次中的1次中，您还将执行条件内的代码，因此最好添加!(k == i && j == l)

- anotherOne

---

我认为这会大大增加算法的时间复杂度，而我至少希望保持在O(n^2)。 - Kennet Emerson

@KennetEmerson，你认为这个有多复杂？ - dreamcrash

@KennetEmerson 我并不是在针对你。我只是觉得那些用源代码回答这种具体问题的人应该考虑一下它对网站动态的影响。问题本身完全没问题，但回答应该更加理论化。如果有人正在寻找可解决他们问题的工作源代码，他们应该发现堆栈溢出对他们没有用，否则只会有越来越多的人不是来学习而是来卸载。 - szpanczyk

@KennetEmerson，使用k和l的循环始终运行3次，无论n的大小如何。 - anotherOne

@Davide - 留出一些空间来进行实际学习。你看，如果有人既想要又知道如何正确地自主学习，他们可以从你的源代码中学到东西。如果他们不知道如何学习，他们可能会感觉已经学到了什么，但实际上并没有。 如果你表达了概念，他们仍然需要真正理解它并将其转化为代码。无论如何，如果一个问题中唯一需要做的就是提供可行的源代码，那么你应该报告这个问题以进行锁定或删除，而不是回答它。 - szpanczyk