LeetCode 题解工作台
沙漏的最大总和
给你一个大小为 m x n 的整数矩阵 grid 。 按以下形式将矩阵的一部分定义为一个 沙漏 ： 返回沙漏中元素的 最大 总和。 注意： 沙漏无法旋转且必须整个包含在矩阵中。 示例 1： 输入： grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]] 输出…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们观察题目发现，每个沙漏就是一个 $3 \times 3$ 的矩阵挖去中间行的首尾两个元素。因此，我们可以从左上角开始，枚举每个沙漏的中间坐标 $(i, j)$，然后计算沙漏的元素和，取其中的最大值即可。 时间复杂度 $O(m \times n)$，其中 和 分别是矩阵的行数和列数。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个大小为 m x n 的整数矩阵 grid 。
按以下形式将矩阵的一部分定义为一个 沙漏 ：
返回沙漏中元素的 最大 总和。
注意：沙漏无法旋转且必须整个包含在矩阵中。
示例 1：
输入：grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]] 输出：30 解释：上图中的单元格表示元素总和最大的沙漏：6 + 2 + 1 + 2 + 9 + 2 + 8 = 30 。
示例 2：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]] 输出：35 解释：上图中的单元格表示元素总和最大的沙漏：1 + 2 + 3 + 5 + 7 + 8 + 9 = 35 。
提示：
m == grid.lengthn == grid[i].length3 <= m, n <= 1500 <= grid[i][j] <= 106
解题思路
方法一：枚举
我们观察题目发现，每个沙漏就是一个 的矩阵挖去中间行的首尾两个元素。因此，我们可以从左上角开始，枚举每个沙漏的中间坐标 ，然后计算沙漏的元素和，取其中的最大值即可。
时间复杂度 ，其中 和 分别是矩阵的行数和列数。空间复杂度 。
class Solution:
def maxSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
for i in range(1, m - 1):
for j in range(1, n - 1):
s = -grid[i][j - 1] - grid[i][j + 1]
s += sum(
grid[x][y] for x in range(i - 1, i + 2) for y in range(j - 1, j + 2)
)
ans = max(ans, s)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m * n) because each 3x3 hourglass is visited once. Space complexity can be O(1) for brute force or O(m * n) if using full prefix sum arrays. Optimization depends on chosen approach. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect questions on how to iterate without index errors when handling the 3x3 hourglass shape.
- question_mark
Look for recognition of overlapping submatrices and opportunities to optimize with prefix sums.
- question_mark
Evaluate how candidates track maximum sums efficiently and avoid redundant calculations.
常见陷阱
外企场景- error
Forgetting that hourglass centers are single elements in the middle row, causing incorrect sums.
- error
Accessing indices outside matrix bounds when looping near edges.
- error
Recomputing entire sums for overlapping hourglasses instead of using sliding updates or prefix sums.
进阶变体
外企场景- arrow_right_alt
Compute minimum sum of an hourglass instead of maximum sum.
- arrow_right_alt
Handle non-square matrices or variable hourglass sizes, e.g., 4x4 patterns.
- arrow_right_alt
Return coordinates of the hourglass with maximum sum along with the sum.