LeetCode 题解工作台
最大的幻方
一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部 相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。 给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k ）。 …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们定义 表示矩阵第 行前 列的元素和，定义 表示矩阵第 列前 行的元素和。则对于任意子矩阵 $(x_1, y_1)$ 到 $(x_2, y_2)$，其第 行的和可以表示为 $\text{rowsum}[i+1][y_2+1] - \text{rowsum}[i+1][y_1]$，其第 列的和可以表示为 $\text{colsum}[x_2+1][j+1] - \text{cols…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
一个 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.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 106
解题思路
方法一：前缀和 + 枚举
我们定义 表示矩阵第 行前 列的元素和，定义 表示矩阵第 列前 行的元素和。则对于任意子矩阵 到 ，其第 行的和可以表示为 ，其第 列的和可以表示为 。
我们枚举所有可能的子矩阵，并检查其是否为幻方。对于每个子矩阵，我们计算其每一行、每一列以及两条对角线的和，判断它们是否相等即可。
时间复杂度 ，空间复杂度 。
class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
rowsum = [[0] * (n + 1) for _ in range(m + 1)]
colsum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1]
colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1]
def check(x1, y1, x2, y2):
val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1]
for i in range(x1 + 1, x2 + 1):
if rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val:
return False
for j in range(y1, y2 + 1):
if colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val:
return False
s, i, j = 0, x1, y1
while i <= x2:
s += grid[i][j]
i += 1
j += 1
if s != val:
return False
s, i, j = 0, x1, y2
while i <= x2:
s += grid[i][j]
i += 1
j -= 1
if s != val:
return False
return True
for k in range(min(m, n), 1, -1):
i = 0
while i + k - 1 < m:
j = 0
while j + k - 1 < n:
i2, j2 = i + k - 1, j + k - 1
if check(i, j, i2, j2):
return k
j += 1
i += 1
return 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on iterating all possible square sizes and validating sums: roughly O(min(m,n)^3) with prefix sums. Space complexity is O(m*n) for prefix sum storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on using prefix sums to avoid recalculating sums for each square.
- question_mark
Expect you to consider all candidate squares and check diagonal sums carefully.
- question_mark
Watch for off-by-one errors when indexing subgrids in the matrix.
常见陷阱
外企场景- error
Forgetting to check both diagonals, leading to false positives.
- error
Recomputing row and column sums repeatedly without prefix sums.
- error
Misindexing when iterating subgrids or when calculating square boundaries.
进阶变体
外企场景- arrow_right_alt
Find the total number of magic squares of all sizes in a grid instead of the largest.
- arrow_right_alt
Return the top-left coordinate of the largest magic square along with its size.
- arrow_right_alt
Allow only distinct integers inside magic squares, increasing validation complexity.