LeetCode题目笔记——2428. 沙漏的最大总和

36 阅读 0 评论 24 点赞

我是靠谱客的博主标致苗条，最近开发中收集的这篇文章主要介绍LeetCode题目笔记——2428. 沙漏的最大总和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 题目描述——截图
- 题目描述
- 题目难度——中等
- 方法一：遍历
- - 代码/Python
- 方法一优化
- - 代码/Python
  - 代码/C++
- 总结

题目描述——截图

这个题是上周的周赛里的第二题，当时做的时候只用了最简单的遍历方法，虽然通过了，但是也挺慢的，后面会有优化。
在这里插入图片描述

题目描述

给你一个大小为 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 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-sum-of-an-hourglass
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目难度——中等

方法一：遍历

根据题目的提示来看，最大的矩阵也不过150×150，数据量还是比较小的，因此我们可以直接遍历，在便利的过程中，以沙漏的中心点作为遍历的下标指引，这个沙漏的计算过程有点想卷积运算，但比卷积简单的多，只要多次加就好。每次计算一个沙漏的和之后，和上一次计算的结果比较，更新答案。

代码/Python

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        total = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                tmp = grid[i][j]
                for k in range(3):
                    tmp += grid[i - 1][j - 1 + k]	# 沙漏上面一行
                    tmp += grid[i + 1][j - 1 + k]	# 沙漏下面一行
                if tmp > total:
                    total = tmp
        
        return total

这个代码提交了几次，最快也只有108ms，还是比较慢的。接下来进行优化。

方法一优化

观察上面的代码，k循环体中每次都要对上下两行进行重复计算，意味着每次有两个数都是相同的，那我们可以借助滑动窗口的思想来对这个方法进行优化，以沙漏中点为中心，每次循环的时候先计算一个窗口（沙漏）的值，和答案进行比较，更新答案，这样能最大化的节约计算量。虽然这里的沙漏比较小，可能这样优化的方法效果不会太明显，但随着沙漏变大，优化效果肯定会是越来越明显的。

代码/Python

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        total = 0
        for i in range(1, m - 1):
            # 每到一行，先加一个window
            window = grid[i][1]
            for k in range(3):      		# 其实这里还能提速，这里给window赋值了两次，
                window += grid[i - 1][k]	# 其实还可以把grid[i-1][k]和grid[i+1][k]
                window += grid[i + 1][k]	# 先求和再赋值给window，总的来说就可以减少3次赋值
            if window > total:      # 新的一行，所以还要比较一次
                total = window
            for j in range(1, n - 2):	# 列只用遍历到倒数第三列
                window -= grid[i][j]			# 看每一列
                window += grid[i][j + 1]		# 移动沙漏中心
                window -= grid[i - 1][j - 1]	# 分别减去和加上左上角，左下角，右上角，右下角
                window += grid[i - 1][j + 2]
                window -= grid[i + 1][j - 1]
                window += grid[i + 1][j + 2]
                if window > total:
                    total = window
        return total

代码/C++

class Solution {
public:
    int maxSum(vector<vector<int>>& grid) {
        int m, n, total, window, i, j, k;
        m = grid.size();
        n = grid[0].size();
        total = 0;
        for(i = 1; i < m - 1; i++){
            window = grid[i][1];
            for(k = 0; k < 3; k++){
                window += grid[i - 1][k] + grid[i + 1][k];
            }
            if(window > total){
                total = window;
            }
            for(j = 1; j < n - 2; j++){
                window -= grid[i][j];			
                window += grid[i][j + 1];	
                window -= grid[i - 1][j - 1];
                window += grid[i - 1][j + 2];
                window -= grid[i + 1][j - 1];
                window += grid[i + 1][j + 2];
                if(window > total){
                    total = window;
                }
            }
        }
        return total;
    }
};