Medium

题目描述

给你一个 m x n 的整数矩阵 grid。

我们定义一个沙漏为矩阵的一部分，形状如下：

a b c
  d
e f g

返回沙漏中元素的最大总和。

注意沙漏不能旋转且必须完全包含在矩阵中。

示例 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.length
  • n == grid[i].length
  • 3 <= m, n <= 150
  • 0 <= grid[i][j] <= 10^6

解题思路

解题思路

这道题要求找到矩阵中所有沙漏形状子矩阵的最大元素和。沙漏形状由7个位置组成：顶部一行的3个元素、中间行的1个中心元素、底部一行的3个元素。

方法一：暴力枚举（推荐） 遍历所有可能的3x3子矩阵，对于每个子矩阵计算其沙漏形状的元素和。具体步骤：

  1. 遍历所有可能的左上角位置(i, j)，确保3x3子矩阵完全在边界内
  2. 对于每个位置，计算沙漏元素和：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]
  3. 维护最大值

方法二：前缀和优化 虽然可以使用前缀和来优化求和过程，但由于沙漏形状不规则，前缀和的优势不明显，而且会增加代码复杂度，因此直接计算更简洁高效。

时间复杂度为O((m-2)(n-2))，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    int maxSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int maxHourglassSum = 0;
        
        for (int i = 0; i <= m - 3; i++) {
            for (int j = 0; j <= n - 3; j++) {
                int currentSum = 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];
                maxHourglassSum = max(maxHourglassSum, currentSum);
            }
        }
        
        return maxHourglassSum;
    }
};

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        max_hourglass_sum = 0
        
        for i in range(m - 2):
            for j in range(n - 2):
                current_sum = (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_hourglass_sum = max(max_hourglass_sum, current_sum)
        
        return max_hourglass_sum

public class Solution {
    public int MaxSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int maxHourglassSum = 0;
        
        for (int i = 0; i <= m - 3; i++) {
            for (int j = 0; j <= n - 3; j++) {
                int currentSum = 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];
                maxHourglassSum = Math.Max(maxHourglassSum, currentSum);
            }
        }
        
        return maxHourglassSum;
    }
}

var maxSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let maxHourglassSum = 0;
    
    for (let i = 0; i <= m - 3; i++) {
        for (let j = 0; j <= n - 3; j++) {
            const currentSum = 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];
            maxHourglassSum = Math.max(maxHourglassSum, currentSum);
        }
    }
    
    return maxHourglassSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O((m-2)(n-2))需要遍历所有可能的3x3子矩阵的左上角位置
空间复杂度O(1)只使用常数级额外空间

相关题目