本文涉及的基础知识点

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] <= 10⁵

前缀和

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))

代码

核心代码

<code>class Solution { -- -->

public:

vector<int> getBiggestThree(vector<vector<int>>& grid) {

const int R = grid.size();

const int 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);

}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。