沙漏的最大总和
难度:
标签:
题目描述
给你一个大小为 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
/*
* 思路：
* 1. 使用Stream API来简化遍历和计算过程。
* 2. 使用嵌套Stream来遍历每个可能的沙漏顶点，并计算总和。
* 3. 使用mapToInt和max来找到最大的沙漏总和。
*/
import java.util.Arrays;
public class Solution {
public int maxHourglassSum(int[][] grid) {
return IntStream.range(0, grid.length - 2)
.flatMap(i -> IntStream.range(0, grid[0].length - 2)
.map(j -> grid[i][j] + grid[i][j + 1] + grid[i][j + 2]
+ grid[i + 1][j + 1]
+ grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2]))
.max()
.orElse(0);
}
}解释
方法:
该题解通过一次遍历来寻找具有最大元素总和的沙漏。对于每个可能的中心点 (i, j)，计算以此点为中心的沙漏形状的元素总和。然后通过内置的max函数在所有沙漏的总和中找到最大值。遍历的起始点是 (1, 1)，结束点是 (m-2, n-2)，确保沙漏形状总是完全包含在矩阵中。
时间复杂度:
O(m*n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到的遍历起始点为 (1, 1)，结束点为 (m-2, n-2)，这是否意味着矩阵的大小至少为3x3？如果矩阵小于3x3，会发生什么？
▷🦆
在计算沙漏总和时，你是如何确保索引不会超出矩阵范围的？例如，对于边界上的中心点 (i, j)，是否有可能尝试访问不存在的元素？
▷🦆
为什么选择遍历中心点，而不是直接遍历每个可能的沙漏的最顶层元素？这种中心点的方法有什么特殊优势吗？
▷🦆
你的算法在计算每个沙漏的总和时是否考虑到了矩阵中的负数元素？在存在负数的情况下，这种方法是否仍然有效？
▷