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

https://leetcode-cn.com/problems/get-biggest-three-rhombus-sums-in-a-grid/

这题关键就在于如何快速计算菱形上覆盖的点的和，可以拆分成为几个部分看：

  1. 假设最上方点为(i, j), 变长为k, 那么最下方点就是(i+2k, j)
  2. 侧面点分别是(i+k, j-k)和(i+k, j+k).
  3. 我们可以统计上面三角形部分覆盖的点的值，记为up[(i, j, k)]，同样可以计算下面三角形部分值，记为 down[(i, j, k)]
  4. 那么整个菱形覆盖的点的和就就是 up[(i, j, k)] + down[(i+2k, j, k-1)]
  5. k=0需要单独进行计算。代码不是特别多，但是写起来需要非常仔细。
class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        n, m = len(grid), len(grid[0])
        values = []
        up, down = {}, {}
        for i in range(n):
            for j in range(m):
                v = grid[i][j]
                up[(i,j,0)] = v
                down[(i, j, 0)] = v

                k = 1
                while True:
                    l, r = j-k,j+k
                    if (i+k) >=n or l < 0 or r >= m: break
                    v += grid[i+k][l] + grid[i+k][r]
                    up[(i, j, k)] = v
                    k += 1

                k = 1
                v = grid[i][j]
                while True:
                    l, r = j-k,j+k
                    if (i-k) <0 or l < 0 or r >= m: break
                    v += grid[i-k][l] + grid[i-k][r]
                    down[(i, j, k)] = v
                    k += 1

        for i in range(n):
            for j in range(m):
                values.append(grid[i][j])
                k = 1
                while True:
                    i2 = i + 2 * k
                    l, r = j-k, j+k
                    if i2 >=n or l < 0 or r >= m:break
                    a = up[(i, j, k)]
                    b = down[(i2, j, k-1)]
                    values.append(a+b)
                    k += 1

        values = list(set(values))
        values.sort(reverse = True)
        return values[:3]