日期: 2026年1月18日

目标

一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

示例 1：

输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12

示例 2：

输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
输出：2

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 10^6

思路

找出 m x n 矩阵中的最大幻方的边长。

暴力枚举顶点与边长，判断是否是幻方。可以记录水平、垂直、主对角线和副对角线上的前缀和，方便幻方判断。另外边长可以从大到小枚举，是幻方就直接返回。

代码

/**
 * @date 2026-01-19 14:59
 */
public class LargestMagicSquare1895 {

    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int l = Math.min(i, j) + 1;
                for (int k = res + 1; k <= l; k++) {
                    if (isMagicSquare(grid, i, j, k)) {
                        res = k;
                    }
                }
            }
        }
        return res;
    }

    public boolean isMagicSquare(int[][] grid, int x, int y, int l) {
        int diagonal1 = 0;
        int diagonal2 = 0;
        for (int k = 0; k < l; k++) {
            diagonal1 += grid[x - k][y - k];
            diagonal2 += grid[x - l + 1 + k][y - k];
        }
        if (diagonal1 != diagonal2) {
            return false;
        }

        for (int i = x - l + 1; i <= x; i++) {
            int sum = 0;
            for (int j = y - l + 1; j <= y; j++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        for (int j = y - l + 1; j <= y; j++) {
            int sum = 0;
            for (int i = x - l + 1; i <= x; i++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        return true;
    }

}

性能