矩阵中最大的三个菱形和

标签: 数组数学矩阵前缀和排序堆（优先队列）

难度: Medium

给你一个 m x n 的整数矩阵 grid 。

菱形和 指的是 grid 中一个正菱形边界上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。

注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。

请你按照降序返回 grid 中三个最大的 互不相同的菱形和 。如果不同的和少于三个，则将它们全部返回。

示例 1：

输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
输出：[228,216,211]
解释：最大的三个菱形和如上图所示。
- 蓝色：20 + 3 + 200 + 5 = 228
- 红色：200 + 2 + 10 + 4 = 216
- 绿色：5 + 200 + 4 + 2 = 211

示例 2：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
- 蓝色：4 + 2 + 6 + 8 = 20
- 红色：9 （右下角红色的面积为 0 的菱形）
- 绿色：8 （下方中央面积为 0 的菱形）

示例 3：

输入：grid = [[7,7,7]]
输出：[7]
解释：所有三个可能的菱形和都相同，所以返回 [7] 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 10⁵

Submission

运行时间: 306 ms

内存: 16.7 MB

class Answer:
    def __init__(self):
        self.ans = [0, 0, 0]
    
    def put(self, x: int):
        _ans = self.ans

        if x > _ans[0]:
            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]
        elif x != _ans[0] and x > _ans[1]:
            _ans[1], _ans[2] = x, _ans[1]
        elif x != _ans[0] and x != _ans[1] and x > _ans[2]:
            _ans[2] = x
    
    def get(self) -> List[int]:
        _ans = self.ans

        return [num for num in _ans if num != 0]


class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        sum1 = [[0] * (n + 2) for _ in range(m + 1)]
        sum2 = [[0] * (n + 2) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                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]
        
        ans = Answer()
        for i in range(m):
            for j in range(n):
                # 单独的一个格子也是菱形
                ans.put(grid[i][j])
                for k in range(i + 2, m, 2):
                    ux, uy = i, j
                    dx, dy = k, j
                    lx, ly = (i + k) // 2, j - (k - i) // 2
                    rx, ry = (i + k) // 2, j + (k - i) // 2
                    
                    if ly < 0 or ry >= n:
                        break
                    
                    ans.put(
                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +
                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +
                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +
                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -
                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])
                    )
        
        return ans.get()

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/get-biggest-three-rhombus-sums-in-a-grid/solutions/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

本题解的主要思路是使用动态规划来计算矩阵中任意菱形的和。首先，构建两个辅助矩阵sum1和sum2来存储从左上到右下和从右上到左下的前缀和。这样可以快速计算出任意大小的菱形和。对于每个可能的菱形中心点，遍历可能的菱形大小，利用前缀和矩阵来计算出这个菱形的总和。使用一个自定义类Answer来维护三个最大的不同的菱形和。这个类有一个方法put来更新这三个最大值，如果新的菱形和比已有的大且不重复，则更新对应的值。最后，使用get方法返回结果。这种方法可以有效地避免重复计算任意菱形的元素和，提高效率。

时间复杂度: O(m*n*min(m,n)^2)

空间复杂度: O(m*n)

# 解题类定义

class Answer:
    def __init__(self):
        self.ans = [0, 0, 0]  # 初始化三个最大菱形和为0

    def put(self, x: int):
        # 更新三个最大的不同菱形和
        if x > self.ans[0]:
            self.ans[0], self.ans[1], self.ans[2] = x, self.ans[0], self.ans[1]
        elif x != self.ans[0] and x > self.ans[1]:
            self.ans[1], self.ans[2] = x, self.ans[1]
        elif x != self.ans[0] and x != self.ans[1] and x > self.ans[2]:
            self.ans[2] = x

    def get(self) -> List[int]:
        return [num for num in self.ans if num != 0]  # 返回非零的最大三个和

# 主解题类

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])  # 获取矩阵的行数和列数
        sum1 = [[0] * (n + 2) for _ in range(m + 1)]  # 前缀和数组1
        sum2 = [[0] * (n + 2) for _ in range(m + 1)]  # 前缀和数组2

        # 构建前缀和矩阵
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                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]
        
        ans = Answer()  # 初始化Answer类
        for i in range(m):
            for j in range(n):
                ans.put(grid[i][j])  # 单个点也视为一个菱形
                for k in range(i + 2, m, 2):  # 遍历所有可能的菱形大小
                    ux, uy = i, j
                    dx, dy = k, j
                    lx, ly = (i + k) // 2, j - (k - i) // 2
                    rx, ry = (i + k) // 2, j + (k - i) // 2
                    
                    if ly < 0 or ry >= n:
                        break  # 超出边界则停止

                    diamond_sum = (
                        sum2[lx + 1][ly + 1] - sum2[ux][uy + 2] +
                        sum1[rx + 1][ry + 1] - sum1[ux][uy] +
                        sum1[dx + 1][dy + 1] - sum1[lx][ly] +
                        sum2[dx + 1][dy + 1] - sum2[rx][ry + 2] -
                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])
                    )  # 计算菱形和
                    ans.put(diamond_sum)
        
        return ans.get()  # 返回最大的三个不同的菱形和

Explore

前缀和矩阵sum1和sum2的设计是用来快速计算菱形的和。sum1从左上到右下的前缀和用于计算左下到右上的斜线和，而sum2从右上到左下的前缀和用于计算右下到左上的斜线和。这样设计的优势在于：不论菱形的中心点在哪里，或者菱形的大小如何，都可以通过这两个前缀和矩阵在常数时间内得出任意斜线的和，极大地简化了计算过程并提高了效率。

在本题解的实现中，通过遍历每个可能的菱形中心点以及从中心向外扩展的不同大小，系统性地考虑了每种可能的菱形。对于每个中心点和每个大小，只计算一次相应的菱形和。因此，不同中心点或不同大小的菱形不会重复计算。这种基于中心点和大小的迭代确保了每个菱形和的唯一性。

在Answer类的put方法中，如果新加入的菱形和与已存在的最大的菱形和相等，则不进行任何操作。这是因为我们希望保留不同的最大菱形和。具体来说，如果新的菱形和等于当前的最大值或第二大值，我们不更新任何值，只有当新的菱形和大于现有的某个值且不等于其他较大值时，我们才更新对应的值。这样可以确保我们存储的是三个最大的、不同的菱形和。

在计算菱形和时，减去的(grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])是为了去除重复计算的角落元素。这四个点具体是菱形的四个顶点，它们在使用前缀和计算整个菱形区域的和时会被计算两次：一次在左对角线和，一次在右对角线和。因此，我们需要从总和中减去这四个顶点的值，以确保每个元素只被计算一次。这种方法确保了最终的菱形和的准确性。