1. 题目解析与核心思路这道来自LeetCode的1878题要求我们在给定的整数矩阵中找出所有可能的菱形计算每个菱形的元素和最终返回和最大的三个不同菱形和不足三个则全部返回。菱形在矩阵中的定义比较特殊它必须是一个正方形旋转45度后的形状且菱形的边界必须由矩阵中的元素组成。1.1 菱形定义与数学表达菱形的数学定义需要明确几个关键参数中心点坐标(i,j)半径r从中心到任意顶点的距离四个顶点坐标分别为(i-r,j), (i,j-r), (ir,j), (i,jr)一个有效的菱形必须满足所有顶点都在矩阵范围内。例如在5x5矩阵中中心点(2,2)可以形成的最大半径是2因为半径为3时顶点(5,2)虽然合法但(2,5)就越界了。1.2 暴力解法的时间复杂度分析最直观的解法是三层循环遍历所有可能的中心点O(mn)遍历所有可能的半径O(min(m,n))遍历菱形上的所有点O(r)这样总时间复杂度达到O(mn*min(m,n)^2)对于100x100的矩阵来说就是1亿次操作显然不够高效。2. 优化解法前缀和与菱形遍历2.1 对角线前缀和预处理我们可以使用类似图像处理中的积分图思想预处理四个方向的对角线前缀和主对角线方向左上到右下副对角线方向右上到左下定义prefix1[i][j]表示从(0,0)到(i,j)的主对角线方向前缀和prefix2[i][j]表示从(0,n-1)到(i,j)的副对角线方向前缀和。这样可以在O(1)时间内计算任意菱形边上的和。2.2 菱形和计算优化对于中心点(i,j)和半径r的菱形上顶点到右顶点的和 prefix1[i][jr] - prefix1[i-r-1][j-1]右顶点到下顶点的和 prefix2[ir][j] - prefix2[i-1][jr1]下顶点到左顶点的和 prefix1[ir][j] - prefix1[i-1][j-r-1]左顶点到上顶点的和 prefix2[i][j-r] - prefix2[i-r-1][j1]总菱形和就是这四个部分的和减去四个顶点被重复计算的部分。这样将单次菱形和计算从O(r)优化到O(1)。3. 完整实现代码与注释def getBiggestThree(grid): m, n len(grid), len(grid[0]) max_radius (min(m, n) - 1) // 2 # 预处理四个方向的前缀和 prefix1 [[0]*(n2) for _ in range(m2)] # 主对角线 prefix2 [[0]*(n2) for _ in range(m2)] # 副对角线 for i in range(1, m1): for j in range(1, n1): prefix1[i][j] prefix1[i-1][j-1] grid[i-1][j-1] prefix2[i][j] prefix2[i-1][j1] grid[i-1][j-1] sums set() for i in range(m): for j in range(n): sums.add(grid[i][j]) # 半径为0的情况 max_r min(i, m-1-i, j, n-1-j) for r in range(1, max_r1): # 计算四个顶点的坐标 top (i-r, j) right (i, jr) bottom (ir, j) left (i, j-r) # 计算四条边的和 sum_top_right prefix1[i][jr1] - prefix1[i-r-1][j1] sum_right_bottom prefix2[ir1][j1] - prefix2[i][jr2] sum_bottom_left prefix1[ir1][j1] - prefix1[i][j-r] sum_left_top prefix2[i1][j-r1] - prefix2[i-r][j1] total sum_top_right sum_right_bottom sum_bottom_left sum_left_top total - grid[top[0]][top[1]] grid[right[0]][right[1]] grid[bottom[0]][bottom[1]] grid[left[0]][left[1]] sums.add(total) # 返回前三大 return sorted(sums, reverseTrue)[:3]4. 复杂度分析与优化验证4.1 时间复杂度对比原始暴力解法时间复杂度O(mn*min(m,n)^2)空间复杂度O(1)优化后的解法预处理O(mn)主循环O(mn*min(m,n))总时间复杂度O(mn*min(m,n))空间复杂度O(mn)对于100x100的矩阵优化后运算量从1亿次降到约50万次效率提升200倍。4.2 边界条件测试用例需要特别注意的测试情况矩阵行数或列数为1所有元素相同的情况最大半径刚好等于min(m,n)//2矩阵中存在负数的情况多个菱形和相同的情况5. 实际应用与扩展思考5.1 图像处理中的应用这种菱形和计算在图像处理中有实际应用比如菱形滤波器设计特定形状的特征提取图像金字塔构建时的采样模式5.2 扩展到其他形状类似的思路可以应用于其他几何形状的和计算矩形标准的前缀和即可三角形需要设计三个方向的前缀和圆形需要近似处理边界像素5.3 并行计算优化由于每个中心点的计算是独立的这个算法非常适合并行化按行或列分块使用多线程或GPU加速分布式计算处理超大矩阵