力扣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()); } };