【C++前缀和】1878. 矩阵中最大的三个菱形和|1897
本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode 1878. 矩阵中最大的三个菱形和
难度分：1897
给你一个 m x n 的整数矩阵 grid 。
菱形和 指的是 grid 中一个正菱形 边界 上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。
注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。
请你按照 降序 返回 grid 中三个最大的 互不相同的菱形和 。如果不同的和少于三个，则将它们全部返回。
示例 1：
输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
输出：[228,216,211]
解释：最大的三个菱形和如上图所示。
- 蓝色：20 + 3 + 200 + 5 = 228
- 红色：200 + 2 + 10 + 4 = 216
- 绿色：5 + 200 + 4 + 2 = 211
示例 2：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
- 蓝色：4 + 2 + 6 + 8 = 20
- 红色：9 （右下角红色的面积为 0 的菱形）
- 绿色：8 （下方中央面积为 0 的菱形）
示例 3：
输入：grid = [[7,7,7]]
输出：[7]
解释：所有三个可能的菱形和都相同，所以返回 [7] 。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 105
前缀和
preSum0[r][c] 记录以gird[r,c]开始的正对角线的前缀和。随着i增加，r,c都增加。
preSum1[r][c] 记录以gird[r,c]开始的反对角线的前缀和。随着i增加，r增加，c减少。
枚举菱形的中心，时间复杂度：O(mn) 枚举菱形的变成时间复杂度：O(min(m,n))，求菱形和，利用前缀和O(1) 总时间复杂度：O(mnmin(m,n))
代码
核心代码
classSolution{public: vector<int>getBiggestThree(vector<vector<int>>& grid){constint R = grid.size();constint C = grid.front().size(); vector<vector<vector<int>>>preSum0(R, vector<vector<int>>(C, vector<int>(1)));auto preSum1 = preSum0;//初始前缀和for(int r =0; r < R; r++){for(int c =0; c < C; c++){for(int r1 = r, c1 = c;(r1 < R)&&(c1 < C); r1++, c1++){ preSum0[r][c].emplace_back(grid[r1][c1]+ preSum0[r][c].back());}for(int r1 = r, c1 = c;(r1 < R)&&(c1 >=0); r1++, c1--){ preSum1[r][c].emplace_back(grid[r1][c1]+ preSum1[r][c].back());}}}//枚举菱形中心 vector<int> ret;for(int r1 =0; r1 < R; r1++){for(int c1 =0; c1 < C; c1++){ ret.emplace_back(grid[r1][c1]);for(int r0 = r1 -1, r2 = r1 +1, c0 = c1 -1, c2 = c1 +1,k=1;(r0 >=0)&&(c0 >=0)&&(r2 < R)&&(c2 < C); r0--, c0--, r2++, c2++,k++){int cur = preSum0[r0][c1][k]+ preSum1[r0 +1][c1 -1][k]+ preSum0[r1 +1][c0 +1][k]+ preSum1[r1][c2][k]; ret.emplace_back(cur);}}}sort(ret.begin(), ret.end(), greater<>()); ret.erase(unique(ret.begin(), ret.end()), ret.end());if(ret.size()>3){ ret.erase(ret.begin()+3,ret.end());}return ret;}};单元测试
vector<vector<int>> grid;TEST_METHOD(TestMethod1){ grid ={{1}};auto res =Solution().getBiggestThree(grid);AssertEx({1}, res);}TEST_METHOD(TestMethod2){ grid ={{2,1}};auto res =Solution().getBiggestThree(grid);AssertEx({2,1}, res);}TEST_METHOD(TestMethod11){ grid ={{3,4,5,1,3},{3,3,4,2,3},{20,30,200,40,10},{1,5,5,4,1},{4,3,2,2,5}};auto res =Solution().getBiggestThree(grid);AssertEx({228,216,211}, res);}TEST_METHOD(TestMethod12){ grid ={{1,2,3},{4,5,6},{7,8,9}};auto res =Solution().getBiggestThree(grid);AssertEx({20,9,8}, res);}TEST_METHOD(TestMethod13){ grid ={{7,7,7}};auto res =Solution().getBiggestThree(grid);AssertEx({7}, res);}扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
