Medium

题目描述

一个 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

解题思路

这道题要求找到网格中最大的魔方阵。魔方阵的特点是所有行和、列和以及对角线和都相等。

核心思路：

  1. 从大到小枚举正方形的边长k，一旦找到满足条件的魔方阵就直接返回
  2. 对于每个可能的边长k，枚举所有可能的起始位置(i,j)
  3. 检查以(i,j)为左上角、边长为k的正方形是否为魔方阵

优化策略： 为了快速计算子矩阵的行和、列和，我们可以使用前缀和数组：

  • rowSum[i][j] 表示第i行前j个元素的和
  • colSum[i][j] 表示第j列前i个元素的和

检查魔方阵的步骤：

  1. 计算第一行的和作为目标和
  2. 检查所有行和是否都等于目标和
  3. 检查所有列和是否都等于目标和
  4. 检查两条对角线和是否都等于目标和

由于题目规模较小(最大50x50)，这种暴力枚举的方法是可行的。时间复杂度为O(min(m,n)^3 * max(m,n))，在给定约束下完全可以接受。

代码实现

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 构建行前缀和
        vector<vector<int>> rowSum(m, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowSum[i][j + 1] = rowSum[i][j] + grid[i][j];
            }
        }
        
        // 构建列前缀和
        vector<vector<int>> colSum(m + 1, vector<int>(n, 0));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colSum[i + 1][j] = colSum[i][j] + grid[i][j];
            }
        }
        
        // 从大到小枚举边长
        for (int k = min(m, n); k >= 1; k--) {
            for (int i = 0; i <= m - k; i++) {
                for (int j = 0; j <= n - k; j++) {
                    if (isMagicSquare(grid, rowSum, colSum, i, j, k)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }
    
private:
    bool isMagicSquare(vector<vector<int>>& grid, vector<vector<int>>& rowSum, 
                       vector<vector<int>>& colSum, int r, int c, int k) {
        // 计算第一行的和作为目标和
        int target = rowSum[r][c + k] - rowSum[r][c];
        
        // 检查所有行和
        for (int i = r; i < r + k; i++) {
            if (rowSum[i][c + k] - rowSum[i][c] != target) {
                return false;
            }
        }
        
        // 检查所有列和
        for (int j = c; j < c + k; j++) {
            if (colSum[r + k][j] - colSum[r][j] != target) {
                return false;
            }
        }
        
        // 检查主对角线
        int diag1 = 0;
        for (int i = 0; i < k; i++) {
            diag1 += grid[r + i][c + i];
        }
        if (diag1 != target) return false;
        
        // 检查反对角线
        int diag2 = 0;
        for (int i = 0; i < k; i++) {
            diag2 += grid[r + i][c + k - 1 - i];
        }
        if (diag2 != target) return false;
        
        return true;
    }
};

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 构建行前缀和
        row_sum = [[0] * (n + 1) for _ in range(m)]
        for i in range(m):
            for j in range(n):
                row_sum[i][j + 1] = row_sum[i][j] + grid[i][j]
        
        # 构建列前缀和
        col_sum = [[0] * n for _ in range(m + 1)]
        for j in range(n):
            for i in range(m):
                col_sum[i + 1][j] = col_sum[i][j] + grid[i][j]
        
        def is_magic_square(r, c, k):
            # 计算第一行的和作为目标和
            target = row_sum[r][c + k] - row_sum[r][c]
            
            # 检查所有行和
            for i in range(r, r + k):
                if row_sum[i][c + k] - row_sum[i][c] != target:
                    return False
            
            # 检查所有列和
            for j in range(c, c + k):
                if col_sum[r + k][j] - col_sum[r][j] != target:
                    return False
            
            # 检查主对角线
            diag1 = sum(grid[r + i][c + i] for i in range(k))
            if diag1 != target:
                return False
            
            # 检查反对角线
            diag2 = sum(grid[r + i][c + k - 1 - i] for i in range(k))
            if diag2 != target:
                return False
            
            return True
        
        # 从大到小枚举边长
        for k in range(min(m, n), 0, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if is_magic_square(i, j, k):
                        return k
        
        return 1

public class Solution {
    public int LargestMagicSquare(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 构建行前缀和
        int[,] rowSum = new int[m, n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowSum[i, j + 1] = rowSum[i, j] + grid[i][j];
            }
        }
        
        // 构建列前缀和
        int[,] colSum = new int[m + 1, n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colSum[i + 1, j] = colSum[i, j] + grid[i][j];
            }
        }
        
        // 从大到小枚举边长
        for (int k = Math.Min(m, n); k >= 1; k--) {
            for (int i = 0; i <= m - k; i++) {
                for (int j = 0; j <= n - k; j++) {
                    if (IsMagicSquare(grid, rowSum, colSum, i, j, k)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }
    
    private bool IsMagicSquare(int[][] grid, int[,] rowSum, int[,] colSum, int r, int c, int k) {
        // 计算第一行的和作为目标和
        int target = rowSum[r, c + k] - rowSum[r, c];
        
        // 检查所有行和
        for (int i = r; i < r + k; i++) {
            if (rowSum[i, c + k] - rowSum[i, c] != target) {
                return false;
            }
        }
        
        // 检查所有列和
        for (int j = c; j < c + k; j++) {
            if (colSum[r + k, j] - colSum[r, j] != target) {
                return false;
            }
        }
        
        // 检查主对角线
        int diag1 = 0;
        for (int i = 0; i < k; i++) {
            diag1 += grid[r + i][c + i];
        }
        if (diag1 != target) return false;
        
        // 检查反对角线
        int diag2 = 0;
        for (int i = 0; i < k; i++) {
            diag2 += grid[r + i][c + k - 1 - i];
        }
        if (diag2 != target) return false;
        
        return true;
    }
}

var largestMagicSquare = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 构建行前缀和
    const rowSum = Array(m).fill(0).map(() => Array(n + 1).fill(0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            rowSum[i][j + 1] = rowSum[i][j] + grid[i][j];
        }
    }
    
    // 构建列前缀和
    const colSum = Array(m + 1).fill(0).map(() => Array(n).fill(0));
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < m; i++) {
            colSum[i + 1][j] = colSum[i][j] + grid[i][j];
        }
    }
    
    function isMagicSquare(r, c, k) {
        // 计算第一行的和作为目标和
        const target = rowSum[r][c + k] - rowSum[r][c];
        
        // 检查所有行和
        for (let i = r; i < r + k; i++) {
            if (rowSum[i][c + k] - rowSum[i][c] !== target) {
                return false;
            }
        }
        
        // 检查所有列和
        for (let j = c; j < c + k; j++) {
            if (colSum[r + k][j] - colSum[r][j] !== target) {
                return false;
            }
        }
        
        // 检查主对角线
        let diag1 = 0;
        for (let i = 0; i < k; i++) {
            diag1 += grid[r + i][c + i];
        }
        if (diag1 !== target) return false;
        
        // 检查反对角线
        let diag2 = 0;
        for (let i = 0; i < k; i++) {
            diag2 += grid[r + i][c + k - 1 - i];
        }
        if (diag2 !== target) return false;
        
        return true;
    }
    
    // 从大到小枚举边长
    for (let k = Math.min(m, n); k >= 1; k--) {
        for (let i = 0; i <= m - k; i++) {
            for (let j = 0; j <= n - k; j++) {
                if (isMagicSquare(i, j, k)) {
                    return k;
                }
            }
        }
    }
    return 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(min(m,n)³ × max(m,n))
空间复杂度O(mn)

详细分析：

  • 时间复杂度：外层枚举边长O(min(m,n))，内层枚举起始位置O(mn)，检查魔方阵需要O(k)时间，总体为O(min(m,n)³ × max(m,n))
  • 空间复杂度：需要存储行前缀和和列前缀和数组，均为O(mn)的空间

相关题目