如何降低N皇后矩阵验证器现有解决方案的时间复杂度

你当前的暴力解法存在两个核心问题：

1. 行、列检查循环硬编码了i<8，只能适配8皇后场景，无法处理任意尺寸的N×N矩阵
2. 四次独立扫描矩阵，存在大量重复遍历操作，且最后两段副对角线检查逻辑完全重复，做了无用功

核心优化逻辑 #

我们可以通过一次遍历矩阵+辅助计数数组的方案，把多次扫描合并为一次，大幅降低运行时开销：

• 用长度为n的数组rowCnt记录每行的皇后数量，要求每行恰好为1
• 用长度为n的数组colCnt记录每列的皇后数量，要求每列恰好为1
• 对于「左上到右下」的主对角线：同一条对角线上的坐标满足i - j值固定，取值范围是[-(n-1), n-1]，我们给这个值加偏移量n-1转换成[0, 2n-2]的数组索引，用长度为2n-1的数组mainDiagCnt计数，要求每条对角线计数≤1
• 对于「右上到左下」的副对角线：同一条对角线上的坐标满足i + j值固定，取值范围是[0, 2n-2]，直接用长度为2n-1的数组antiDiagCnt计数，要求每条对角线计数≤1

优化后代码实现 #

public static boolean solveMatrix(int[][] matrix) {
    int n = matrix.length;
    // 非方阵直接不符合要求，返回false
    if (matrix[0].length != n) {
        return false;
    }

    int[] rowCnt = new int[n];
    int[] colCnt = new int[n];
    int[] mainDiagCnt = new int[2 * n - 1];
    int[] antiDiagCnt = new int[2 * n - 1];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                // 任意维度计数超标直接提前返回
                if (++rowCnt[i] > 1) return false;
                if (++colCnt[j] > 1) return false;
                int mainIdx = i - j + n - 1;
                if (++mainDiagCnt[mainIdx] > 1) return false;
                int antiIdx = i + j;
                if (++antiDiagCnt[antiIdx] > 1) return false;
            }
        }
    }

    // 校验每行每列恰好有1个皇后
    for (int i = 0; i < n; i++) {
        if (rowCnt[i] != 1 || colCnt[i] != 1) {
            return false;
        }
    }

    return true;
}

优化效果说明 #

• 时间复杂度仍然是O(n²)，这是N皇后验证的理论下限（最少需要遍历完所有n²个元素确认皇后位置），但实际运行时只需要一次矩阵遍历，比原来四次遍历的暴力法快3~4倍
• 空间复杂度从原来的O(1)变成O(n)，属于极小的空间换时间开销，对于常规n≤1000的场景完全可以忽略
• 修复了原代码硬编码8、副对角线重复检查的bug，适配任意尺寸的N×N方阵验证

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