力扣1878.矩阵中最大的三个菱形和

力扣1878.矩阵中最大的三个菱形和

• 斜前缀和

  • 遍历矩阵元素，同时求当前点左下右下两位置的前缀和
  • 枚举每个菱形中心，遍历边长

•   int sum1[101][101];
    int sum2[101][101];
    class Solution {
    public:
        vector<int> getBiggestThree(vector<vector<int>>& grid) {
            int n = grid.size() , m = grid[0].size();
    
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1];
                    sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1];
                }
    
            set<int> S;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    S.insert(grid[i-1][j-1]);
                    for(int k=1;i + k <= n && i - k >= 1 && j + k <= m && j - k >= 1;k++)
                    {
                        int a = sum1[i+k][j] - sum1[i][j-k];
                        int b = sum1[i][j+k] - sum1[i-k][j];
                        int c = sum2[i + k][j] - sum2[i][j + k];
                        int d = sum2[i][j - k] - sum2[i - k][j];
                        S.insert(a+b+c+d - grid[i+k-1][j-1] + grid[i-k-1][j-1]);
                    }
                    while(S.size() > 3) S.erase(S.begin());
                }
            return vector<int> (S.rbegin(),S.rend());
        }
    };