侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【模拟】沙漏的最大总和【力扣第 313 场周赛】

GabrielxD
2022-10-02 / 0 评论 / 0 点赞 / 20 阅读 / 420 字 / 正在检测是否收录...

题目

6193. 沙漏的最大总和


给你一个大小为 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.length
  • n == grid[i].length
  • 3 <= m, n <= 150
  • 0 <= grid[i][j] <= 10^6

解题

方法一:模拟

思路

根据题目给出的沙漏的定义,枚举矩阵中的每个沙漏计出总和并维护一个最大总和(max)返回即可。

具体来说,枚举矩阵中的 grid[1m1][1n1]grid[1\sim m-1][1 \sim n-1] 的位置作为沙漏中心,然后把沙漏的每一个点加起来算出该沙漏点总和。

代码

class Solution {
    public int maxSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int max = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                int sum = 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];
                max = Math.max(max, sum);
            }
        }
        return max;
    }
}
0

评论区