Medium

题目描述

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

菱形和是指构成网格中正菱形形状边界的元素之和。菱形必须是正方形旋转 45 度的形状，每个角都位于网格单元格的中心。下面的图像显示了四个有效的菱形形状以及应包含在每个菱形和中的相应有色单元格：

注意菱形可以有 0 的面积，如右下角的紫色菱形所示。

返回网格中最大的三个不同菱形和的降序排列。如果少于三个不同的值，则返回所有值。

示例 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 <= 50
  • 1 <= grid[i][j] <= 10^5

解题思路

这道题需要找到网格中所有菱形的和，并返回最大的三个不同值。

解题思路：

  1. 理解菱形结构：菱形是正方形旋转45度形成的，包括面积为0的菱形（单个格子）和更大的菱形。

  2. 枚举所有可能的菱形：

    • 对于每个格子作为菱形中心，枚举不同大小的菱形
    • 菱形大小用半径r表示，r=0时是单个格子，r>0时形成真正的菱形边界

  3. 计算菱形和：

    • 当r=0时，菱形和就是当前格子的值
    • 当r>0时，需要计算菱形四条边的和，注意避免重复计算顶点

  4. 维护最大的三个不同值：

    • 使用集合去重，然后维护最大的三个值
    • 可以用优先队列或直接用集合然后排序

算法步骤：

  • 遍历每个可能的菱形中心点(i,j)
  • 对于每个中心点，枚举所有可能的菱形半径r
  • 计算每个菱形的边界和
  • 将所有不同的和值加入结果集合
  • 返回最大的三个值

时间复杂度主要取决于菱形数量，由于网格大小限制在50x50，所以效率可以接受。

代码实现

class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        set<int> sums;
        
        // 遍历每个可能的菱形中心
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 半径为0，就是单个格子
                sums.insert(grid[i][j]);
                
                // 尝试更大的菱形半径
                for (int r = 1; r <= min(i, min(j, min(m-1-i, n-1-j))); r++) {
                    int sum = 0;
                    
                    // 计算菱形四条边的和
                    // 上边：从左上到右上
                    for (int k = 0; k < r; k++) {
                        sum += grid[i-r+k][j-k];  // 左上到顶点
                        sum += grid[i-r+k][j+k];  // 顶点到右上
                    }
                    
                    // 下边：从左下到右下  
                    for (int k = 0; k < r; k++) {
                        sum += grid[i+r-k][j-k];  // 左下到底点
                        sum += grid[i+r-k][j+k];  // 底点到右下
                    }
                    
                    // 减去重复计算的四个顶点
                    sum -= grid[i-r][j];  // 上顶点
                    sum -= grid[i][j-r];  // 左顶点  
                    sum -= grid[i+r][j];  // 下顶点
                    sum -= grid[i][j+r];  // 右顶点
                    
                    sums.insert(sum);
                }
            }
        }
        
        vector<int> result(sums.rbegin(), sums.rend());
        if (result.size() > 3) {
            result.resize(3);
        }
        return result;
    }
};

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        sums = set()
        
        # 遍历每个可能的菱形中心
        for i in range(m):
            for j in range(n):
                # 半径为0，就是单个格子
                sums.add(grid[i][j])
                
                # 尝试更大的菱形半径
                max_radius = min(i, j, m-1-i, n-1-j)
                for r in range(1, max_radius + 1):
                    rhombus_sum = 0
                    
                    # 计算菱形四条边的和
                    # 上边：从左上到右上
                    for k in range(r):
                        rhombus_sum += grid[i-r+k][j-k]  # 左上到顶点
                        rhombus_sum += grid[i-r+k][j+k]  # 顶点到右上
                    
                    # 下边：从左下到右下
                    for k in range(r):
                        rhombus_sum += grid[i+r-k][j-k]  # 左下到底点
                        rhombus_sum += grid[i+r-k][j+k]  # 底点到右下
                    
                    # 减去重复计算的四个顶点
                    rhombus_sum -= grid[i-r][j]  # 上顶点
                    rhombus_sum -= grid[i][j-r]  # 左顶点
                    rhombus_sum -= grid[i+r][j]  # 下顶点
                    rhombus_sum -= grid[i][j+r]  # 右顶点
                    
                    sums.add(rhombus_sum)
        
        result = sorted(sums, reverse=True)
        return result[:3]

public class Solution {
    public int[] GetBiggestThree(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        HashSet<int> sums = new HashSet<int>();
        
        // 遍历每个可能的菱形中心
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 半径为0，就是单个格子
                sums.Add(grid[i][j]);
                
                // 尝试更大的菱形半径
                int maxRadius = Math.Min(Math.Min(i, j), Math.Min(m-1-i, n-1-j));
                for (int r = 1; r <= maxRadius; r++) {
                    int sum = 0;
                    
                    // 计算菱形四条边的和
                    // 上边：从左上到右上
                    for (int k = 0; k < r; k++) {
                        sum += grid[i-r+k][j-k];  // 左上到顶点
                        sum += grid[i-r+k][j+k];  // 顶点到右上
                    }
                    
                    // 下边：从左下到右下
                    for (int k = 0; k < r; k++) {
                        sum += grid[i+r-k][j-k];  // 左下到底点
                        sum += grid[i+r-k][j+k];  // 底点到右下
                    }
                    
                    // 减去重复计算的四个顶点
                    sum -= grid[i-r][j];  // 上顶点
                    sum -= grid[i][j-r];  // 左顶点
                    sum -= grid[i+r][j];  // 下顶点
                    sum -= grid[i][j+r];  // 右顶点
                    
                    sums.Add(sum);
                }
            }
        }
        
        var sortedSums = sums.OrderByDescending(x => x).Take(3).ToArray();
        return sortedSums;
    }
}

var getBiggestThree = function(grid) {
    const m = grid.length, n = grid[0].length;
    const sums = new Set();
    
    // 遍历每个可能的菱形中心
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 半径为0，就是单个格子
            sums.add(grid[i][j]);
            
            // 尝试更大的菱形半径
            const maxRadius = Math.min(i, j, m-1-i, n-1-j);
            for (let r = 1; r <= maxRadius; r++) {
                let sum = 0;
                
                // 计算菱形四条边的和
                // 上边：从左上到右上
                for (let k = 0; k < r; k++) {
                    sum += grid[i-r+k][j-k];  // 左上到顶点
                    sum += grid[i-r+k][j+k];  // 顶点到右上
                }
                
                // 下边：从左下到右下
                for (let k = 0; k < r; k++) {
                    sum += grid[i+r-k][j-k];  // 左下到底点
                    sum += grid[i+r-k][j+k];  // 底点到右下
                }
                
                // 减去重复计算的四个顶点
                sum -= grid[i-r][j];  // 上顶点
                sum -= grid[i][j-r];  // 左顶点
                sum -= grid[i+r][j];  // 下顶点
                sum -= grid[i][j+r];  // 右顶点
                
                sums.add(sum);
            }
        }
    }
    
    const result = Array.from(sums).sort((a, b) => b - a);
    return result.slice(0, 3);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × min(m,n)²)，其中m和n是网格的行数和列数。对于每个中心点，最多枚举min(m,n)个半径，每个菱形计算需要O(r)时间
空间复杂度O(m × n × min(m,n))，用于存储所有可能的菱形和值，最坏情况下每个菱形都有不同的和

相关题目