企业官网建设流程全解析

前两天刷力扣每日一题时碰到1878这道“矩阵中最大的三个菱形和”。很多人一看“菱形”两个字，下意识觉得是几何题，动手才发现它真正考的是枚举、前缀和、去重这三板斧。题目不算难，但如果你没把“菱形在网格里到底长什么样”想清楚，代码会写得非常别扭。这篇文章就从我的实际做题过程出发，把题目定义、暴力思路为什么慢、对角线前缀和怎么写、以及我踩过的几个边界坑完整过一遍。适合正在刷二维矩阵类题目、想搞懂对角线前缀和用法的朋友，也适合准备面试时查漏补缺的读者。

1. 题目到底在算什么：菱形、菱形和、以及最容易理解偏的地方

1.1 菱形在矩阵里的离散形态

先看题目给出的定义：菱形的四条边长度相等，且每条边都与网格的对角线方向平行。注意，这里说的网格对角线方向，指的是矩阵里斜着45度的那两个方向，也就是“左上到右下”和“右上到左下”。

因为顶点必须落在格点上，边又只能沿斜对角方向走，所以一个菱形其实可以被“中心点 + 半径”唯一确定。中心是一个格点，半径 k 表示从中心向上下左右四个方向各走多少步。举个例子，中心在 (2, 2)，k = 1 时，四个顶点就是：

• 上顶点 (1, 2)
• 右顶点 (2, 3)
• 下顶点 (3, 2)
• 左顶点 (2, 1)

把这四个顶点沿斜线连起来，就得到一个旋转了45度的正方形。k = 0 时菱形退化成一个格子，也就是中心格本身。这个退化情况题目是认的，后面代码里必须单独处理，很多人就是挂在这一点上。

这里要特别提醒一句：这道题里的“菱形和”指的是边框上所有格子的数值之和，不是把菱形围住的内部区域一起算。虽然从几何直觉上，一个旋转45度的正方形很自然地会让人想到“实心区域”，但题目既然说的是“由菱形边框上的数字形成的和”，那就是只算边框。我最初没注意这个区别，按实心区域去推公式，推了半天发现跟预期结果对不上，回头看题才反应过来。

1.2 枚举四个顶点为什么不可行

最简单的暴力想法是：枚举所有可能的四个顶点，判断它们能否构成合法菱形，然后计算边框和。这个思路方向没错，但实现起来非常痛苦。

原因有两个。第一，一个菱形可以被很多组“四个顶点”重复表达吗？不会，菱形本来就由四个顶点唯一确定，但你在枚举顶点时很难保证同一个菱形不被重复创建。第二，为了判断“四条边是否沿对角线方向”以及“四条边是否等长”，你需要写一堆坐标判断逻辑，代码又长又容易错。更关键的是，就算你把所有菱形都枚举出来了，每个边框上格子的数量是 O(k) 的，直接把格子值加一遍，总复杂度会到 O(mn * min(m,n)^2) 甚至更高。

所以更聪明的思路是：不要从顶点切入，而是从“中心 + 半径”这个自然参数切入。一个中心、一个半径，就能确定一个菱形，枚举状态数一下子就清楚了。

2. 核心枚举框架：中心遍历加半径遍历

2.1 用中心点确定所有菱形

刚才已经说过，菱形由中心 (i, j) 和半径 k 唯一确定。因此算法主框架非常简单：

1. 遍历矩阵中的每一个格子，把它当作菱形中心。
2. 对每个中心，尝试所有可能的半径 k。
3. 对每个合法的 (i, j, k)，用 O(1) 时间算出菱形边框和。
4. 把结果放入集合去重。
5. 最后从集合里挑出最大的三个值。

半径 k 的最大值不是随便取的。菱形的四个顶点必须落在矩阵内部，所以受限于中心到上下左右四条边的距离：

k <= min(i, j, m - 1 - i, n - 1 - j)

比如中心在左上角 (0, 0)，那么 k 最大只能是 0，因为它没法向左边或上边延伸。这个 limit 的计算很简单，但漏掉它就是越界访问。

2.2 为什么暴力累加边框会被卡住

假设我们不用任何前缀和，对于每个 (i, j, k)，直接沿着四条边把格子值加一遍。四条边每一条有 k 个格子，所以一次求和是 O(k)。枚举中心是 O(mn)，每个中心的最大半径是 O(min(m,n))，那么总复杂度是：

O(mn * min(m,n)^2)

如果矩阵是 100 x 100，min(m,n) = 100，粗略估算是 1e8 量级。C++ 在极限情况下可能勉强跑过，Python 基本没戏。而且这里还没有算常数：每条边你要写四个方向循环，循环里做数组下标运算，常数还不小。

这时候自然要想到前缀和。如果我们能在 O(1) 时间内求出任意一条“对角线线段”的和，那么整个菱形边框拆成四条斜线段，总体也是 O(1)，总复杂度就能降到 O(mn * min(m,n))。这就是这道题的核心优化点。

2.3 从四边拼接到顶点去重

在引入前缀和之前，先理清边框怎么由四条斜线段拼出来。

还是以中心 (i, j)、半径 k 为例，四个顶点记为 U、R、D、L。四条边分别是：

• U 到 R：方向为“右下”，也就是主对角线方向。
• R 到 D：方向为“左下”，也就是副对角线方向。
• D 到 L：方向为“左上”，实际上就是“右下”的反方向。
• L 到 U：方向为“右上”，实际上就是“左下”的反方向。

如果我们分别求出四条线段的完整和，四个顶点会被重复计算。比如 U 既属于 U-R 这条边，又属于 L-U 这条边。所以完整公式是：

边框和 = (U-R线段和) + (R-D线段和) + (D-L线段和) + (L-U线段和) - grid[U] - grid[R] - grid[D] - grid[L]

这里减去的四个顶点值，正好是它们被多加的那一次。

3. 对角线前缀和：斜线段 O(1) 求和的实现原理

3.1 两个方向的后缀和数组

矩阵里的斜线分成两类：主对角线方向（右下）和副对角线方向（左下）。我们分别建两个数组：

• dr[i][j]：从 (i, j) 出发，沿着右下方向一直走到边界，这条对角线上所有格子值的和。
• dl[i][j]：从 (i, j) 出发，沿着左下方向一直走到边界，这条对角线上所有格子值的和。

构建的时候从下往上、从右往左倒着算：

dr[i][j] = grid[i][j] + (i+1 < m && j+1 < n ? dr[i+1][j+1] : 0) dl[i][j] = grid[i][j] + (i+1 < m && j-1 >= 0 ? dl[i+1][j-1] : 0)

为什么叫“后缀和”？因为它记录的是从当前点一直延伸到矩阵边界的所有格子之和。如果要从一条斜线上截取中间一段，就用“起点后缀和”减去“终点再往后一格”的后缀和，这样中间那段就剩下来了。

3.2 查询公式与边界处理

假设要查询主对角线方向从 (a, b) 到 (c, d) 的线段和，并且这条线段确实落在同一条右下方向的斜线上，也就是满足 a <= c 且 b <= d：

sumDR(a,b,c,d) = dr[a][b] - (c+1 < m && d+1 < n ? dr[c+1][d+1] : 0)

这里减去的是终点右下方那一格继续延伸的部分。如果终点已经在边界，减去的部分就是 0，所以需要做越界判断，不能直接访问数组下标。

副对角线方向从 (a, b) 到 (c, d)，要求 a <= c 且 b >= d：

sumDL(a,b,c,d) = dl[a][b] - (c+1 < m && d-1 >= 0 ? dl[c+1][d-1] : 0)

因为副对角线方向是向左下走的，终点再往下一格时，列号要减一，边界判断也要对应处理。

3.3 菱形四条边怎么套用这两个数组

这一步写代码时最容易乱。我建议先把四个顶点算出来，再对照方向一个一个套：

注意下边和左边，我没有直接按 D 到 L 的方向查，而是反着查。因为sumDR只支持“起点在左上、终点在右下”，而 D 到 L 方向是左上，和前缀和方向相反。反过来的话，L 到 D 正好是右下方向，满足要求。左边同理。

这个反向查询的思路，本质上就是：一条斜线段是无向的，前缀和只能从左上往右下或从左下往右上方向计算，那我就从另一头作为起点去查，结果完全一样。

3.4 画图验证一个 k = 1 的菱形

以中心 (2, 2)、k = 1 为例，四顶点：

• U = (1, 2)
• R = (2, 3)
• D = (3, 2)
• L = (2, 1)

边框应该是 U、R、D、L 这四个格子，对吗？不对，k = 1 时，每条边只取一个格子，四条边各一个格子，最终边框就是 U、R、D、L 本身，四个格子，不含中心。

用公式验证：U-R 线段和 = grid[U] + grid[R]；R-D 线段和 = grid[R] + grid[D]；D-L 线段和反查 = grid[L] + grid[D]；L-U 线段和反查 = grid[U] + grid[L]。四段相加后，四个顶点各出现了两次，减去一次四个顶点，剩余正好是四个顶点各一次。对，k = 1 边框就是四个顶点格子，和中心无关。

k = 2 时，四条边每边有两个格子，加上顶点衔接，边框一共 8 个格子。这个规律验证下来，边框格子数永远是 4k，k = 0 时是 1 个中心格。

4. 完整代码实现与关键细节

4.1 C++ 版本

下面是我整理后的 C++ 实现，加了注释。

class Solution { public: vector<int> getBiggestThree(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // 主对角线方向（右下）后缀和 vector<vector<int>> dr(m, vector<int>(n, 0)); for (int i = m - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { dr[i][j] = grid[i][j]; if (i + 1 < m && j + 1 < n) dr[i][j] += dr[i + 1][j + 1]; } } // 副对角线方向（左下）后缀和 vector<vector<int>> dl(m, vector<int>(n, 0)); for (int i = m - 1; i >= 0; --i) { for (int j = 0; j < n; ++j) { dl[i][j] = grid[i][j]; if (i + 1 < m && j - 1 >= 0) dl[i][j] += dl[i + 1][j - 1]; } } auto sumDR = [&](int a, int b, int c, int d) -> int { int res = dr[a][b]; if (c + 1 < m && d + 1 < n) res -= dr[c + 1][d + 1]; return res; }; auto sumDL = [&](int a, int b, int c, int d) -> int { int res = dl[a][b]; if (c + 1 < m && d - 1 >= 0) res -= dl[c + 1][d - 1]; return res; }; set<int> sums; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { // k = 0，退化菱形 sums.insert(grid[i][j]); int limit = min({i, j, m - 1 - i, n - 1 - j}); for (int k = 1; k <= limit; ++k) { int ui = i - k, uj = j; // 上顶点 int ri = i, rj = j + k; // 右顶点 int di = i + k, dj = j; // 下顶点 int li = i, lj = j - k; // 左顶点 int border = 0; border += sumDR(ui, uj, ri, rj); // U -> R border += sumDL(ri, rj, di, dj); // R -> D border += sumDR(li, lj, di, dj); // L -> D，反向表示 D -> L border += sumDL(ui, uj, li, lj); // U -> L，反向表示 L -> U // 四个顶点被多算了一次，减去一个顶点值 border -= grid[ui][uj] + grid[ri][rj] + grid[di][dj] + grid[li][lj]; sums.insert(border); } } } vector<int> ans; for (auto it = sums.rbegin(); it != sums.rend() && ans.size() < 3; ++it) ans.push_back(*it); return ans; } };

这里用了一个set<int>，既去重又能自动排序，最后从后往前取三个就是最大的三个不同值。数据量小，每次 insert 的 log 成本完全可以接受。如果担心grid[i][j]的累加值超过 int 范围，可以把数组类型都换成long long。按力扣的约数范围来算，int 其实是够的，但严谨一点用long long会更安心，特别是矩阵尺寸接近上限时。

4.2 Python 版本

class Solution: def getBiggestThree(self, grid: List[List[int]]) -> List[int]: m, n = len(grid), len(grid[0]) dr = [[0] * n for _ in range(m)] dl = [[0] * n for _ in range(m)] for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): dr[i][j] = grid[i][j] if i + 1 < m and j + 1 < n: dr[i][j] += dr[i + 1][j + 1] for i in range(m - 1, -1, -1): for j in range(n): dl[i][j] = grid[i][j] if i + 1 < m and j - 1 >= 0: dl[i][j] += dl[i + 1][j - 1] def sum_dr(a, b, c, d): res = dr[a][b] if c + 1 < m and d + 1 < n: res -= dr[c + 1][d + 1] return res def sum_dl(a, b, c, d): res = dl[a][b] if c + 1 < m and d - 1 >= 0: res -= dl[c + 1][d - 1] return res ans_set = set() for i in range(m): for j in range(n): ans_set.add(grid[i][j]) limit = min(i, j, m - 1 - i, n - 1 - j) for k in range(1, limit + 1): ui, uj = i - k, j ri, rj = i, j + k di, dj = i + k, j li, lj = i, j - k border = 0 border += sum_dr(ui, uj, ri, rj) border += sum_dl(ri, rj, di, dj) border += sum_dr(li, lj, di, dj) border += sum_dl(ui, uj, li, lj) border -= grid[ui][uj] + grid[ri][rj] + grid[di][dj] + grid[li][lj] ans_set.add(border) return sorted(ans_set, reverse=True)[:3]

Python 版本逻辑和 C++ 完全一致，唯一需要注意的是min(i, j, m - 1 - i, n - 1 - j)这个 limit 可能为 0，所以 k 要从 1 开始循环，k = 0 的情况在一开始单独加入grid[i][j]。

4.3 复杂度分析

预处理两个对角线数组是 O(mn)。枚举中心需要 O(mn)，每个中心的可选半径是 O(min(m,n))。由于每次查菱形边框是四个 O(1) 查询，所以总时间复杂度是：

O(mn * min(m,n))

空间上只多了两个 m x n 的数组，外加一个 set，总体是 O(mn)。这个复杂度下，100 x 100 的矩阵完全没问题，就算矩阵放大到 250 左右也能扛住。

5. 常见问题、边界条件与排查经验

5.1 三个最大和必须互不相同

题目要求的是“最大的三个互不相同的菱形和”。如果不用集合去重，直接建一个数组把所有和装进去，然后排序取前三个，很可能取到重复值，比如有两个不同的菱形算出同一个和，那前三个里就会出现一个并列项。正确做法是用set去重，或者每次都判断一下是否已经出现过。我用set是因为它顺带完成了排序，取前三很方便。

5.2 漏掉 k = 0 的退化菱形

k = 0 时菱形只是一个格子，这个和也必须参与比较。如果把 k 从 1 开始枚举，完全没有考虑单格情况，结果就会漏掉候选。矩阵里如果只有一种菱形和，那答案永远应该是矩阵中某个格子的值，而不是空集合。所以我在进入中心循环后，第一件事就是先把grid[i][j]放进集合。

5.3 半径上限算错导致越界

limit 一定要取四个方向的最小值，少一个都不行。比如中心 (0, 0)，m - 1 - i很大，n - 1 - j也很大，但i和j都是 0，所以 limit 等于 0。如果只按min(m - 1 - i, n - 1 - j)来算，k = 1 时上顶点和左顶点坐标变成负数，访问数组直接越界，轻则结果错误，重则运行时崩溃。

我一般会把四个方向写全：

limit = min(i, j, m - 1 - i, n - 1 - j)

不要图省事只取左右或只取上下。

5.4 四条线段端点去重

如果不做顶点去重，计算出来的“边框和”会比真实值大，而且随着 k 增大，误差固定是四个顶点的值之和。这个问题在代码 review 时很难一眼看出来，最好是在本地用一个 3 x 3 或 5 x 5 的小矩阵手算一遍。比如 3 x 3 全 1 矩阵，中心 (1, 1)、k = 1 的菱形边框应该是 4，如果代码忘了减顶点，会算出 8。这个例子特别适合当自测用例。

5.5 对角线前缀和的边界判断

查询时减去的“下一格”可能已经超出矩阵范围，比如终点在最后一行，c + 1 == m，就不能访问dr[c+1][d+1]。这里必须用条件判断，而不是随便给一个默认值。如果减多了，结果会变成负数，后续排序取前三时完全错乱。我可以给你一个快速自查的方法：把所有减法分支都写成“存在才减，不存在就减 0”的语义。

5.6 自测用例建议

我刷题时常用的两个小用例：

输入: grid = [[3, 0, 3], [0, 0, 0], [3, 0, 3]]

所有非零格子是四个角，中心是 0。k = 1 的中心菱形边框正好是四个 3，和是 12；k = 0 的单格里最大也是 3。所以三个最大不同和应该是 [12, 3]。

输入: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

这个矩阵小，你可以手算所有菱形和，验证代码输出。我自己第一次写出来，就是靠这种 3 x 3 手工算，把顶点去重问题揪出来的。

6. 延伸一下：如果题目改成实心菱形区域怎么办

这道题的菱形和只看边框，但有些变形题会要求计算“菱形覆盖的所有格子之和”。如果你遇到这种变体，上面的对角线线段求和方法就不够了，因为边框只覆盖 O(k) 个格子，而实心区域覆盖 O(k^2) 个格子。当时我研究这个变体时发现一个非常巧妙的做法：把矩阵旋转 45 度，菱形就变成了一个正常的正方形。

具体来说，把原坐标 (i, j) 映射到：

u = i + j v = i - j + (n - 1)

这里加n - 1是为了让 v 的下标从 0 开始，避免负数。映射之后，一个中心为 (i, j)、半径为 k 的实心菱形，在 (u, v) 坐标系里变成了一个轴对齐的矩形区域：

u 的范围：[i + j - k, i + j + k] v 的范围：[i - j + (n - 1) - k, i - j + (n - 1) + k]

建立一个二维数组，把每个grid[i][j]放进pos[u][v]，其他位置填 0，然后对这个数组做二维前缀和。查询矩形区域和就是 O(1)，整体复杂度同样是 O(mn * min(m,n))。

这个思路的核心启发是：矩阵题目里的很多复杂几何形状，换一个坐标系看可能就变成规则矩形。不过这只是针对实心变体题的思路扩展，本题直接用对角线前缀和就够，不用上来就搞坐标旋转。写在这里是给大家留一个思考方向，万一以后碰到类似的变形题，不至于从零开始。

回到这道 1878 题本身，我个人在实际操作中的体会是：拿到题目先别急着写代码，花两分钟把 k = 1、k = 2 的菱形在纸上画出来，明确哪些格子属于边框，哪些属于内部，再决定用哪套求和工具。对角线前缀和其实并不难，难的是把四条边的方向和顶点去重理顺。只要这一步想清楚，整道题的代码基本就是照着公式填。最后再提醒一句：提交之前一定用 3 x 3 的手算用例过一遍，尤其是 k = 0 和顶点去重这两个点，踩过一次之后你就会记得特别牢。