魔法师 (@Constanline) 在 Leetcode每日一题 —— 1878. 矩阵中最大的三个菱形和 中发帖
思路
没想到什么特别合适的算法,就只能遍历了。
首先为了方便计算每条边所在格子的和,我们可以先把所有从顶点开始对角线上格子的和存起来,这样借助前缀和可以O(1)计算菱形和。
然后就是开始遍历了,我是外层遍历所有格子作为顶点,内层遍历可能的大小,存到结果中。
代码
class Solution {
public int[] getBiggestThree(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 存储 左上-右下对角线 右上-坐下对角线 的和
int[][] lrd = new int[m + 1][n + 1];
int[][] rld = new int[m + 1][n + 2];
/...