当前位置: 首页 > biancheng >正文

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;
    }
};

在这里插入图片描述
  经过优化后的方法打败了99.89%,四舍五入就是100了,哈哈哈哈,但是这个内存消耗有点多,明明只用到了常数,这是点解呢,想不通。

总结

  因为几乎要遍历整个矩阵,因此时间是O(M×N),过程中只用到了几个变量,所以空间是O(1),其他有用一行代码直接解决的,虽然思路也差不多,但那种写法很取巧,暂时就不考虑那种了。

相关文章:

  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)
  • 持续精进,改变自己