当前位置: 首页> 娱乐> 明星 > 力扣1878.矩阵中最大的三个菱形和

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

时间:2025/7/9 7:33:11来源:https://blog.csdn.net/Pisasama/article/details/140224029 浏览次数:0次

力扣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());}};
    
关键字:力扣1878.矩阵中最大的三个菱形和

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: