在 N x N 矩阵中寻找局部最小值

1. 概述

本文将探讨如何在一个 N x N 的二维矩阵中寻找局部最小值的问题。

我们将先定义局部最小值的概念，并通过一个示例说明。

然后，我们先介绍一个朴素解法，再改进为更高效的解法。

2. 问题定义

假设我们有一个 N x N 的整数矩阵，每个元素都是唯一的。我们的任务是找出其中任意一个局部最小值。

✅ 局部最小值（Local Minimum）：在一个二维矩阵中，一个单元格的值如果小于其所有相邻单元格的值，则该单元格就是局部最小值。
相邻单元格包括上下左右四个方向（如果存在）。

示例

考虑如下 4x4 的矩阵：

Example1

其中三个局部最小值分别是：

(1,1) = 1
(2,3) = 2
(4,3) = 8

这些单元格都比它们的相邻单元格小。因此，这三个中的任意一个都可以作为答案。

3. 朴素方法

3.1 思路

核心思想：从任意一个单元格出发，不断向值更小的相邻单元格移动，直到找到一个值小于所有相邻单元格的单元格 —— 也就是局部最小值。

这其实是一个深度优先搜索（DFS）的过程。

3.2 实现

Cell FindLocalMinimumNaive(int N, int[][] M) {
    return FindLocalMinimum(new Cell(0, 0));
}

Cell GetNextCell(Cell current, int[][] M) {
    int x = current.row;
    int y = current.col;
    int val = M[x][y];
    Cell next = current;

    if (x > 0 && M[x - 1][y] < val) {
        val = M[x - 1][y];
        next = new Cell(x - 1, y);
    }
    if (y > 0 && M[x][y - 1] < val) {
        val = M[x][y - 1];
        next = new Cell(x, y - 1);
    }
    if (x < N - 1 && M[x + 1][y] < val) {
        val = M[x + 1][y];
        next = new Cell(x + 1, y);
    }
    if (y < N - 1 && M[x][y + 1] < val) {
        val = M[x][y + 1];
        next = new Cell(x, y + 1);
    }

    return next;
}

Cell FindLocalMinimum(Cell current) {
    Cell next = GetNextCell(current, M);
    if (next.equals(current)) {
        return current;
    } else {
        return FindLocalMinimum(next);
    }
}

3.3 时间复杂度分析

每个单元格最多被访问一次。
每次访问最多检查 4 个相邻单元格。
总体复杂度为 **O(N²)**。

4. 分治法（Divide and Conquer）

4.1 思路

核心思想：将矩阵划分为四个象限子矩阵，每次递归地在包含局部最小值的那个子矩阵中查找。

具体步骤如下：

找出中间行和中间列中的最小值所在单元格 minCell。
找出 minCell 的最小相邻单元格 nextCell。
局部最小值一定在 nextCell 所在的子矩阵中。

✅ 为什么这样可以缩小范围？因为中间行/列中最小的那个单元格已经是当前层最小值，如果它还有更小的邻居，说明局部最小值必然存在于那个方向。

4.2 实现

Cell FindLocalMinimumDivideConquer(int[][] M) {
    return FindLocalMinimum(M);
}

Cell FindLocalMinimum(int[][] M) {
    int n = M.length;
    int midRow = n / 2;
    int midCol = n / 2;

    // 找到中间行和中间列中最小的单元格
    Cell minRowCell = getMinInRow(midRow, M);
    Cell minColCell = getMinInColumn(midCol, M);
    Cell minCell = M[minRowCell.row][minRowCell.col] < M[minColCell.row][minColCell.col] ?
                   minRowCell : minColCell;

    Cell nextCell = GetNextCell(minCell, M);

    if (nextCell.equals(minCell)) {
        return minCell;
    } else if (nextCell.row < midRow) {
        if (nextCell.col < midCol) {
            return FindLocalMinimum(extractTopLeft(M, midRow, midCol));
        } else {
            return FindLocalMinimum(extractTopRight(M, midRow, midCol));
        }
    } else {
        if (nextCell.col < midCol) {
            return FindLocalMinimum(extractBottomLeft(M, midRow, midCol));
        } else {
            return FindLocalMinimum(extractBottomRight(M, midRow, midCol));
        }
    }
}

4.3 时间复杂度分析

每次递归处理的矩阵大小是前一次的一半。
每次递归需要扫描中间行和列，共约 2N 个单元格。
总扫描次数为：2N + N + N/2 + ... ≈ 4N。

✅ **总时间复杂度为 O(N)**。

5. 总结

方法	时间复杂度	说明
朴素法	O(N²)	实现简单，但效率一般
分治法	O(N)	更高效，适合大规模矩阵

如果只是找一个局部最小值，分治法明显优于 DFS。
分治法利用了中间行/列的最小值特性，逐步缩小搜索范围，效率更高。
在实际工程中，若矩阵规模较大，建议使用分治法。

Persistence

REST

Security