[特殊字符] LeetCode 做题笔记（一）：1878. 矩阵中最大的三个菱形和

LeetCode 做题笔记一1878. 矩阵中最大的三个菱形和题目链接1878. 矩阵中最大的三个菱形和难度中等 |语言Java |标签数组、数学、矩阵、前缀和、枚举 题目理解给定一个m x n的整数矩阵grid菱形和指的是菱形边界上的元素之和。菱形定义为正方形旋转45度四个角必须落在格子上且可以为面积为0的单点菱形。要求返回矩阵中三个最大的、互不相同的菱形和按降序排列。 关键要点只计算菱形的边界不包含内部菱形边长可以为0即单个点结果要去重不足3个时返回全部 解题思路暴力枚举 TreeSet维护核心思想数据范围较小m, n ≤ 100可以直接枚举所有可能的菱形步骤拆解1️⃣ 枚举菱形中心 半径遍历每个格子(i, j)作为菱形的中心点枚举菱形的半径k从0开始表示边长对于半径为k的菱形四个顶点坐标为上: (i-k, j) 下: (ik, j) 左: (i, j-k) 右: (i, jk)2️⃣ 边界合法性检查// 确保四个顶点都在矩阵范围内if(i-k0||ikm||j-k0||jkn){break;// 更大半径肯定也越界}3️⃣ 计算菱形边界和半径为0直接取grid[i][j]半径0沿四条边累加注意四个顶点只算一次4️⃣ 维护前三大不重复值使用TreeSet自动去重 排序保持大小不超过3 代码实现JavaclassSolution{publicint[]getBiggestThree(int[][]grid){intmgrid.length,ngrid[0].length;// TreeSet自动去重升序排列我们最后反转即可TreeSetIntegerresultsnewTreeSet();// 枚举每个点作为菱形中心for(inti0;im;i){for(intj0;jn;j){// 半径为0的菱形单点results.add(grid[i][j]);// 保持最多3个元素if(results.size()3){results.pollFirst();// 移除最小值}// 枚举更大半径intk1;while(i-k0ikmj-k0jkn){// 计算菱形边界和intsum0;// 上→右从 (i-k, j) 到 (i, jk)for(intstep0;stepk;step){sumgrid[i-kstep][jstep];}// 右→下从 (i, jk) 到 (ik, j)for(intstep0;stepk;step){sumgrid[istep][jk-step];}// 下→左从 (ik, j) 到 (i, j-k)for(intstep0;stepk;step){sumgrid[ik-step][j-step];}// 左→上从 (i, j-k) 到 (i-k, j)for(intstep0;stepk;step){sumgrid[i-step][j-kstep];}results.add(sum);if(results.size()3){results.pollFirst();}k;}}}// 转为降序数组返回int[]ansnewint[results.size()];intidxans.length-1;for(intnum:results){ans[idx--]num;}returnans;}}⚡ 优化技巧前缀和加速可选如果追求极致性能可预处理对角线前缀和// 预处理两条对角线方向的前缀和// diag1: 左上→右下diag2: 右上→左下int[][]diag1newint[m1][n1];int[][]diag2newint[m1][n1];for(inti0;im;i){for(intj0;jn;j){diag1[i1][j1]grid[i][j]diag1[i][j];diag2[i1][j]grid[i][j]diag2[i][j1];}}这样计算任意对角线段和可做到O(1)整体复杂度从 O(mnk²) 降至 O(mnk)。 复杂度分析方法时间复杂度空间复杂度暴力枚举O(m·n·min(m,n)²)O(1)不计结果集前缀和优化O(m·n·min(m,n))O(m·n) 实际测试中由于数据范围小暴力法已足够通过 总结 易错点✅收获几何枚举题的坐标变换技巧Java中TreeSet的使用pollFirst()移除最小值迭代器默认升序边界和与区域和的区别❌易错点菱形顶点重复计算每条边累加时注意端点半径枚举的边界条件while而非for更易控制结果去重 降序输出的细节TreeSet转数组时注意顺序