难度: Medium
给你一个大小为 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运行时间: 50 ms
内存: 18.4 MB
class Solution:
def maxSum(self, grid: List[List[int]]) -> int:
return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +
grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]
for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))
该题解通过一次遍历来寻找具有最大元素总和的沙漏。对于每个可能的中心点 (i, j)，计算以此点为中心的沙漏形状的元素总和。然后通过内置的max函数在所有沙漏的总和中找到最大值。遍历的起始点是 (1, 1)，结束点是 (m-2, n-2)，确保沙漏形状总是完全包含在矩阵中。
时间复杂度: O(m*n)
空间复杂度: O(1)
class Solution:
def maxSum(self, grid: List[List[int]]) -> int:
# 遍历矩阵中所有可能的沙漏中心
return max(
# 计算每个沙漏形状的元素总和
grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +
grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]
for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1)
)
是的，题解中的算法确实要求矩阵的大小至少为3x3，因为沙漏形状包括一个中心点和其上下各三个元素，共7个元素。如果矩阵小于3x3，例如2x2或更小，那么在执行遍历时，range(1, len(grid)-1)将为空，因此不会执行任何遍历或计算操作，这意味着算法在这种情况下不会返回任何结果。
在算法中，通过仅将中心点 (i, j) 的范围限制在 (1, 1) 到 (m-2, n-2) 之间，可以确保以中心点为中心的沙漏形状的所有元素都在矩阵的有效范围内。这样，无论是中心点还是其周围的点，都不会超出矩阵的边界，从而避免了访问不存在的元素。
遍历中心点而非沙漏的最顶层元素使算法的逻辑更简单明了，因为每个沙漏都可以围绕其中心点对称地定义。从中心点开始，可以直接向上和向下扩展来获取全部的沙漏元素。如果遍历顶层元素，则必须同时考虑顶部、中心和底部的位置关系，这在编程上可能导致更复杂的索引计算。中心点的方法直观并减少了错误的可能性。
算法在计算沙漏的总和时确实包括了矩阵中的所有元素，无论它们是正数还是负数。即便矩阵中存在负数，这种方法也是有效的，因为它通过比较所有可能的沙漏形状的总和来找出最大值。如果矩阵中包含负数，这些负数将被计入总和中，可能会影响哪一个沙漏被认为是最大的，但算法本身在处理这种情况时仍然是正确的。