N×N矩阵中大于所有相邻元素坐标的高效查找方法

不存在完全跳过单元格检查、不做邻域比较就能找出所有符合条件位置的方法。
原因很简单：题目给出的矩阵元素是任意自然数，没有排序、值域限制这类前置约束，四邻域局部最大值没有全局可推导的传递特征——你没检查过的单元格，完全有可能刚好满足峰值条件，没有任何捷径可以绕开对潜在候选点的校验。那些能做到对数时间复杂度的峰值查找算法，只适用于「找任意一个峰值」的场景，会漏掉其余符合条件的位置，根本满足不了本题要返回所有有效位置的要求。

虽然没法完全跳过检查，但可以通过优化把实际比较次数压到远低于逐单元格硬做4次比较的水平：

• 边界判断裁剪：矩阵外的邻域值固定为-1，而矩阵内元素都是自然数（≥0），所以所有边界单元格天然满足「外侧邻域小于自身」的条件，不需要做对应方向的比较：第一行的点不用比上方、最后一行不用比下方、第一列不用比左方、最后一列不用比右方，直接砍掉边界点近一半的比较量。
• 预筛候选集：先逐行扫描，只保留比左右邻域都大的行局部极大值作为候选点——非行极大值的点已经不满足「大于左右邻域」的要求，直接排除，不需要再做上下方向的比较。通常经过这一步筛选，候选点的数量会远小于N²，对剩下的候选点只需要校验上下两个方向的大小即可，整体比较次数能降60%以上。
• 比较结果复用：按从左到右、从上到下的顺序遍历时，相邻点的比较结果可以直接复用：比如判断当前点(i,j)是否大于左侧点(i,j-1)的结果，本质上就是之前判断(i,j-1)是否小于右侧点(i,j)的结果，不需要重复计算，能把单候选点的平均比较次数从4次压到2次以内。

def find_all_local_peaks(matrix):
    n = len(matrix)
    if n == 0:
        return []
    peaks = []
    for i in range(n):
        for j in range(n):
            current = matrix[i][j]
            # 边界邻域直接取-1
            up = matrix[i-1][j] if i > 0 else -1
            down = matrix[i+1][j] if i < n-1 else -1
            left = matrix[i][j-1] if j > 0 else -1
            right = matrix[i][j+1] if j < n-1 else -1
            if current > up and current > down and current > left and current > right:
                peaks.append((i, j))
    return peaks

上述基础实现的时间复杂度是O(N²)，结合前面的预筛选、结果复用优化后，实际运行效率会有明显提升，但时间复杂度的下界依然是O(N²)——毕竟最坏情况下（比如矩阵元素严格交替大小，每个点都是候选），你还是得检查完所有单元格才能拿到完整结果。

内容的提问来源于stack exchange，提问作者Wizard