矩阵中最大的三个菱形和

题目描述

题目讲解

菱形是一个“旋转 45° 的正方形”，它的四个角必须满足：

中心点: (i,j)
上角：从中心向上走 k 步 → (i-k, j)
右角：从中心向右走 k 步 → (i, j+k)
下角：从中心向下走 k 步 → (i+k, j)
左角：从中心向左走 k 步 → (i, j-k)
+ 解释 int maxK = min({i, m - 1 - i, j, n - 1 - j});

计算以 (i, j) 为中心时，菱形能扩展到的最大边长 k.

要保证四个角都在矩阵内：

i - k >= 0
i + k < m
j - k >= 0
j + k < n

得到 k 的上限:

k <= i
k <= m - 1 - i
k <= j
k <= n - 1 - j

故最大的 k 是

maxK = min({i, m - 1 - i, j, n - 1 - j});

具体流程

代码

c++
python
java
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        // m: 矩阵的行数
        // n: 矩阵的列数
        int m = grid.size();
        int n = grid[0].size();
        // 存储不同的菱形和
        set<int> st;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 遍历每个格子
                st.insert(grid[i][j]);
                if (st.size() > 3) st.erase(st.begin());
                //  计算以 (i, j) 为中心时，菱形能扩展到的最大步数 k.
                int maxK = min({i, m - 1 - i, j, n - 1 - j});
                for (int k = 1; k <= maxK; ++k) {
                    int sum = 0;

                    // 上 -> 右（包含上，不含右）
                    // 遍历从上角 → 右角的斜边(45° 斜线)，不包含右角，因为右角会在下一条边中作为起点被计算一次.
                    for (int t = 0; t < k; ++t) {
                        int x = i - k + t;
                        int y = j + t;
                        sum += grid[x][y];
                    }

                    // 右 -> 下（包含右，不含下）
                    for (int t = 0; t < k; ++t) {
                        int x = i + t;
                        int y = j + k - t;
                        sum += grid[x][y];
                    }

                    // 下 -> 左（包含下，不含左）
                    for (int t = 0; t < k; ++t) {
                        int x = i + k - t;
                        int y = j - t;
                        sum += grid[x][y];
                    }

                    // 左 -> 上（包含左，不含上）
                    for (int t = 0; t < k; ++t) {
                        int x = i - t;
                        int y = j - k + t;
                        sum += grid[x][y];
                    }

                    st.insert(sum);
                    if (st.size() > 3) st.erase(st.begin());
                }
            }
        }

        // 从大到小输出
        vector<int> ans(st.rbegin(), st.rend());
        return ans;
    }
};