LeetCode 题解工作台
矩阵中最大的三个菱形和
给你一个 m x n 的整数矩阵 grid 。 菱形和 指的是 grid 中一个正菱形 边界 上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。 注意，菱形可以是一个面积为 0 的区域，如上图中右下角的…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们可以预处理得到两个前缀和数组 和 ，其中 表示以 $(i, j)$ 为末尾的左上对角线上的元素之和，而 表示以 $(i, j)$ 为末尾的右上对角线上的元素之和。 接下来，我们枚举每个位置 $(i, j)$，先将 加入有序集合 中，然后枚举菱形的边长 ，那么以 $(i, j)$ 为中心点、边长为 的菱形的和为：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个 m x n 的整数矩阵 grid 。
菱形和 指的是 grid 中一个正菱形 边界 上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。
注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。
请你按照 降序 返回 grid 中三个最大的 互不相同的菱形和 。如果不同的和少于三个，则将它们全部返回。
示例 1：
输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]] 输出：[228,216,211] 解释：最大的三个菱形和如上图所示。 - 蓝色：20 + 3 + 200 + 5 = 228 - 红色：200 + 2 + 10 + 4 = 216 - 绿色：5 + 200 + 4 + 2 = 211
示例 2：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]] 输出：[20,9,8] 解释：最大的三个菱形和如上图所示。 - 蓝色：4 + 2 + 6 + 8 = 20 - 红色：9 （右下角红色的面积为 0 的菱形） - 绿色：8 （下方中央面积为 0 的菱形）
示例 3：
输入：grid = [[7,7,7]] 输出：[7] 解释：所有三个可能的菱形和都相同，所以返回 [7] 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 1001 <= grid[i][j] <= 105
解题思路
方法一：枚举菱形中心点 + 前缀和 + 有序集合
我们可以预处理得到两个前缀和数组 和 ，其中 表示以 为末尾的左上对角线上的元素之和，而 表示以 为末尾的右上对角线上的元素之和。
接下来，我们枚举每个位置 ，先将 加入有序集合 中，然后枚举菱形的边长 ，那么以 为中心点、边长为 的菱形的和为：
我们将这个值加入有序集合 中，同时保证有序集合 的大小不超过 ，最后将有序集合 中的元素逆序输出即可。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
m, n = len(grid), len(grid[0])
s1 = [[0] * (n + 2) for _ in range(m + 1)]
s2 = [[0] * (n + 2) for _ in range(m + 1)]
for i, row in enumerate(grid, 1):
for j, x in enumerate(row, 1):
s1[i][j] = s1[i - 1][j - 1] + x
s2[i][j] = s2[i - 1][j + 1] + x
ss = SortedSet()
for i, row in enumerate(grid, 1):
for j, x in enumerate(row, 1):
l = min(i - 1, m - i, j - 1, n - j)
ss.add(x)
for k in range(1, l + 1):
a = s1[i + k][j] - s1[i][j - k]
b = s1[i][j + k] - s1[i - k][j]
c = s2[i][j - k] - s2[i - k][j]
d = s2[i + k][j] - s2[i][j + k]
ss.add(
a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]
)
while len(ss) > 3:
ss.remove(ss[0])
return list(ss)[::-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate optimize the brute-force method for larger grids?
- question_mark
Does the candidate understand the importance of only keeping the top three distinct sums?
- question_mark
Can the candidate effectively apply sorting and prefix sums in their solution?
常见陷阱
外企场景- error
Not efficiently calculating rhombus sums for larger grids, leading to timeouts.
- error
Ignoring the requirement to maintain only the top three distinct sums, potentially causing unnecessary memory usage.
- error
Misunderstanding the rhombus shape, resulting in incorrect sum calculations or missed valid rhombuses.
进阶变体
外企场景- arrow_right_alt
Finding the top 5 or 10 distinct rhombus sums instead of the top 3.
- arrow_right_alt
Applying the solution to grids with different dimensions, such as rectangular grids.
- arrow_right_alt
Adapting the approach to handle non-square rhombus shapes.