1. 先搞明白题目在问什么这道题你光看标题“网络信号最好的坐标”很容易以为是个贪心或者数学优化题实际上 LeetCode 1620 是一个标准的坐标几何枚举题。它给你一堆信号塔的坐标和发射功率让你在一个有限范围内找一个整数坐标点使得信号强度加起来最大。范围不大坐标上限是 50信号塔数量最多 50 个所以暴力枚举完全跑得动。核心公式其实就一句话对于每个整数坐标点遍历所有信号塔计算距离如果距离小于等于功率就把 ⌊功率 / (1 距离)⌋ 累加起来最后取信号强度最大的那个坐标。题目还加了一个条件如果多个点信号强度相同返回字典序最小的那个也就是 x 尽量小x 相同就 y 尽量小。我第一次看到这个题的时候第一反应是“这会不会要用三分搜索或者最近邻之类的玩意”毕竟网络信号、坐标最优点这种词很容易让人往计算几何方向联想。但看完数据范围就释然了坐标范围只有 0 到 50信号塔最多 50 个整个网格也就 51×51 个候选点每个点最多算 50 次距离总共 2601×50 13 万次操作这个量级连优化都懒得优化直接暴力就是最优解。这类题我在实际面试中也遇到过类似的变体比如“在网格上找信号覆盖最强的位置”或者把信号塔换成传感器、基站本质上都是同一个套路。它考察的其实不是你会不会高深的算法而是你愿不愿意老老实实把数据范围读完、敢不敢直接暴力。很多人在面试里一看到“最优坐标”这种字眼就开始设计复杂算法反而把简单题做复杂了这是很可惜的事。这道题还有个值得注意的点题目要求的是整数坐标点不是连续坐标。千万不要去想什么“对 x 求导等于 0”信号强度函数在这个定义下根本不可导因为它用的是一个固定功率除以距离加一的形式只在离散网格上成立。所以枚举就是最自然的解法。2. 信号强度计算的数学细节2.1 信号衰减公式到底怎么理解题目给的信号强度公式是signal floor(power / (1 distance))这里的 distance 是欧几里得距离也就是 sqrt((x - xi)² (y - yi)²)。注意这个公式里有个“1”它的作用是防止距离为 0 时除零同时也能让信号衰减得更平滑一些。实际通信工程里一般用自由空间路径损耗衰减跟距离的平方成正比但 LeetCode 这里为了简化直接用的线性衰减所以距离对信号的影响没那么剧烈。用这个公式看当你在信号塔正上方时distance 0信号强度就是 power相距 1 个单位时信号变成 power/2相距 3 个单位时变成 power/4。也就是说距离每增加“1 当前距离”这么多信号就减半一次。但因为我们用的是向下取整所以距离稍微大一点信号强度就可能降到 0。有一个很容易踩的坑题目说“如果距离大于 power则该塔信号为 0”这其实是为了避免出现“(distance 1) power 时 floor(power / (distance 1)) 自动变成 0”的情况但并不是说所有距离大于功率的塔信号都严格等于 0。比如 power 10distance 9那么 floor(10 / (9 1)) 1这时候虽然 distance power但信号强度已经是 1 了。如果 distance 20此时公式理论上算出来的 floor(10 / 21) 0也等于无效。所以判断条件用“distance power”还是“distance 1 power”会产生微小的差别虽然在多数情况下结果一致但为了防止边界问题最严谨的做法还是老老实实判断 distance power 才贡献信号。2.2 为什么枚举顺序能顺便解决字典序题目要求信号相同时取字典序最小的坐标即 x 越小越好x 相同时 y 越小越好。这个问题如果你单独去想可能还要写个比较器但在枚举框架里你只需要把 x 和 y 的循环顺序设计成从小到大然后用一个严格大于的判定条件去更新最大值就行了。也就是说初始化 bestX 0bestY 0bestSignal -1或者任何负数然后从 x 0 到 50y 0 到 50 依次遍历。计算当前点的信号强度 cur只有当 cur bestSignal 时才更新最优坐标。这样即使在后面遇到信号强度相同但字典序更大的点也不会覆盖之前已经记录的更小坐标天然就满足了题目要求。如果你脑子一抽把循环写成从大到小或者用了 来判断那最终返回的坐标就不一定是字典序最小的了。这个点看上去很细节但真在面试里写错了面试官一眼就能看出来你思考不周。最后提交报错的话排查起来也比较隐蔽因为它只在多个点信号相同的场景触发。3. 三种解法从暴力到优雅3.1 解法一全场枚举最稳的 0 思考实现第一种方案就是标准的全场枚举。先遍历一遍信号塔找到所有塔的坐标范围然后在这个范围内遍历所有整数点对每个点累加从所有塔收到的信号强度最后选出最大值。我直接用 Java 写了一个参考实现public int[] bestCoordinate(int[][] towers, int radius) { int minX 50, maxX 0, minY 50, maxY 0; for (int[] tower : towers) { minX Math.min(minX, tower[0]); maxX Math.max(maxX, tower[0]); minY Math.min(minY, tower[1]); maxY Math.max(maxY, tower[1]); } int bestX 0, bestY 0, bestSignal -1; for (int x 0; x 50; x) { for (int y 0; y 50; y) { int cur 0; for (int[] tower : towers) { int dx x - tower[0]; int dy y - tower[1]; double d Math.sqrt(dx * dx dy * dy); if (d radius) { cur (int) Math.floor(tower[2] / (1 d)); } } if (cur bestSignal) { bestSignal cur; bestX x; bestY y; } } } return new int[]{bestX, bestY}; }这里我没有真的去遍历信号塔的包围盒而是直接扫 0 到 50 的全网格。反正全网格也就 2601 个点每个点算 50 个欧氏距离性能完全没问题。这样代码还更短也不用多处理 towers 为空时的边界情况因为 towers 长度至少为 1。对每个点计算信号时先把 dx 和 dy 分别搞出来再算平方和的平方根最后用 Math.floor 做向下取整。注意这里如果你用强制类型转换(int)对于正数是向下取整对于负数则相当于向零取整但我们的信号值恒为 0 或正数所以两个写法等价。不过为了跟题目公式严格保持一致我建议用 Math.floor 处理避免以后把代码改成别的场景时出问题。3.2 解法二提前修剪遍历范围减少无用计算如果信号塔的坐标范围很小比如都集中在 [10, 20] 这个区间而你还在 0 到 50 的全网格上扫那就白白浪费了大量计算。更聪明一点的做法是先算出所有塔的 x 和 y 的边界再在这个包围盒里枚举这样能省掉很多明显不可能成为最优解的点。但有一个需要注意的地方信号最强的点不一定落在塔的包围盒内。比如两个塔分别在 (0,0) 和 (50,50)它们的包围盒是 [0,50]×[0,50]几乎覆盖全图所以不影响。但反过来想如果只有一个塔在 (0,0)另一个在 (0,10)最强的点固然在塔附近但也可能出现在 (0,1)、(0,2) 这种不在包围盒内的坐标上不对这些坐标在包围盒内。实际上完全有可能出现最强点在包围盒之外的反例所以边界剪枝必须保守——至少把包围盒向外扩展 radius 的距离才安全。编码上就是int minX 50, maxX 0, minY 50, maxY 0; for (int[] tower : towers) { minX Math.min(minX, tower[0]); maxX Math.max(maxX, tower[0]); minY Math.min(minY, tower[1]); maxY Math.max(maxY, tower[1]); } int startX Math.max(0, minX - radius); int endX Math.min(50, maxX radius); int startY Math.max(0, minY - radius); int endY Math.min(50, maxY radius); for (int x startX; x endX; x) { for (int y startY; y endY; y) { // 后续计算相同 } }这种优化的前提是你要理解如果某个点距离所有塔都超过了 radius那么它的信号强度一定是 0而所有塔所在的位置本身至少有一个塔在发射信号所以最优解一定在至少一个塔的 radius 范围内也就是在包围盒扩展 radius 后的矩形内。这个剪枝逻辑是严谨的不是拍脑袋拍出来的。实测下来如果信号塔坐标分布得很离散这种枚举范围剪枝可以节省 40% 甚至更多的无效坐标点计算。虽然 LeetCode 上这道题暴力也能过但写出这种优化起码说明你想问题更全面面试的时候是个加分项。3.3 解法三做一点距离公式的优化避免重复计算平方根平方根计算在计算机里是比较贵的操作虽然现代 CPU 对 sqrt 也有硬件指令但在 51×51×50 这个量级下其实无所谓。我这里的优化思路是先把信号塔的功率 radius 平方一下得到 maxDistSquare然后在判断距离是否有效时用 dxdx dydy maxDistSquare 替代 sqrt 再比较这样就省掉了每次计算距离时的开方操作。不过信号强度公式里还需要用到真实的距离值 1 d 作为分母所以这个方法只能省掉“判断是否在范围内”的那次开方真正计算信号强度时仍然需要开方。如果你实在想省掉所有开方操作就得对分母做变换但那样会引入浮点精度问题得不偿失。所以我在实现里采用了一种折中先快速判断是否在接收范围内如果不在就直接跳过省掉后续的 math floor 和除法如果在范围内再开方算真实信号强度。这样在多数塔分布稀疏的场景下能减少大量无效的乘除运算。写出来大概是这样的代码片段int maxDistSquare radius * radius; for (int[] tower : towers) { int dx x - tower[0]; int dy y - tower[1]; int distSquare dx * dx dy * dy; if (distSquare maxDistSquare) { continue; } double d Math.sqrt(distSquare); cur (int) Math.floor(tower[2] / (1 d)); }这是我在做题时比较偏爱的一种写法因为它在保持代码逻辑清晰的同时能明显减少无效计算实测性能也更好。如果你用 C你还可以用 int 类型全程计算把最后的比较条件转换成避免浮点误差的形式但这个对 Java 来说没必要毕竟这个题根本没要求你手写 sqrt。4. 常见问题与排查技巧实录4.1 字典序问题为什么我返回的坐标总是“错”的我在实际跑用例的时候第一版代码用的是“先算一个 max再扫描一遍等于 max 的坐标取最小”这种两遍式的写法看起来逻辑没毛病但就是会踩坑。原因很简单你如果第一遍扫描时用 来更新最优坐标那么循环顺序是 x 从 0 到 50、y 从 0 到 50那你最终拿到的反而是字典序最大的那个坐标。后来我改成一遍扫描加严格大于就把这个问题彻底解决了。如果你是在本地 IDE 里调试想肉眼验证是不是字典序的锅可以专门构造一个所有点信号都一样的用例比如只有一个信号塔功率 radius 0那整个网格上只有塔本身那个点的信号等于 power其他点全是 0这种情况下返回塔的位置就行看不出问题。要构造出有多个相同最优值的情况得让两个塔的覆盖范围对称这样在两个塔之间可能会出现信号值一样的点。4.2 半径处理radius 参数和塔的 power 是两回事这个题最容易让新手晕的点是radius 表示的是“塔的覆盖半径”就是距离超过这个值信号就衰减为 0power 是塔的发射功率决定近距离处的信号强度。两者在公式中承担的角色完全不一样。我在写题的时候第一时间就把它俩搞混了结果就是信号强度算出来乱七八糟一度以为是浮点精度问题。后来重新读题发现 distance radius 时不贡献信号而信号强度计算里的 power 是另一个量才把代码改对。建议你拿到题目后先把这两个变量用不同的命名区分开比如maxDistance和signalPower能减少很多低级错误。4.3 浮点误差引发的边界问题理论上如果两个坐标点的信号强度数学上相等但因为你用了 double 运算可能出现 5.999999999 和 6.000000001 这种微小差异。在这个题里由于信号强度公式最后要向下取整成 int所以这种误差反而会被“抹平”一部分但也不能完全排除边界情况。我见过有人把这个题的信号强度累加成 double最后再比较 double 大小结果因为微小的浮点误差导致返回了错误坐标。更稳妥的做法是每次计算单个塔的信号后立即取整到 int再累加到一个 int 变量里。这样整个过程都是整数运算完全避开浮点比较的不确定性。这也是我在参考实现里用cur (int) Math.floor(tower[2] / (1 d))而不是cur tower[2] / (1 d)再去比较的原因。4.4 全网格扫描 vs 包围盒扫描的取舍如果你看一些题解会发现不少人直接用 0 到 50 的全网格扫描也许会觉得那才是标准答案。但其实两者都可以通过只不过全网格扫描代码更短不容易漏点包围盒扫描则能节省一些计算量但必须注意扩展 radius否则可能漏掉最优解。我建议在比赛或面试中优先写全网格扫描因为简单、不可能错时间复杂度完全可接受。等你写完基本版本确认逻辑正确后再顺手加上包围盒优化这样即使优化写错了也不至于影响正确性。但如果你是先写优化版再翻车排查起来会比较痛苦因为你需要同时验证两件事一是枚举范围有没有漏点二是信号强度计算对不对。这里我整理了一个速查表方便你快速对照自己的代码问题所在症状可能原因解决办法强信号坐标答案和预期不符更新条件用了 覆盖了更小坐标改回严格大于循环从小到到输出坐标始终是 (0,0)初始化 bestSignal 0但存在信号更弱的点被跳过初始化为 -1范围很小但结果偏差包围盒没有扩展 radius对塔范围扩展 radius 后 clamp 到 [0,50]答案算出来差 1信号强度公式忘了向下取整或者用了四舍五入确认用 floor 处理大数据量超时每个坐标都手动调 sqrt 和 floor 太多次先判断 distSquare radius²再执行 sqrt4.5 关于“空塔”情况的特殊处理LeetCode 的约束里 towers.length 1所以严格来说不会遇到空数组。但如果你在扩展这个题或者面试官临时改题问“如果 towers 为空怎么办”那你需要在开头就判断一下如果 towers 长度为 0直接返回 {0, 0} 即可。这种防御性编程的习惯在实际项目里非常重要。我还遇到过一种特殊的输入所有塔的功率都是 0。这种情况下所有坐标的信号强度都是 0按照字典序最小的原则应该返回 (0, 0)。如果你的 bestSignal 初始化为 -1那么第一次循环到 (0,0) 就会把它更新成 bestSignal 0最终正确返回 (0,0)。所以初始化成 -1 是很有讲究的它能正确处理所有信号都是 0 的极端场景。5. 同类问题与思维拓展做完了 LeetCode 1620你会发现其实很多题都是这个套路的变体给你一堆有影响的点或范围在一个有限网格上评估所有位置最后找一个“最大/最小”的格点。比如热词里经常出现的 LeetCode 热门 100 题、周赛题以及 1273、073 这类编号题很多都能归到网格枚举、二维前缀和、差分数组这些框架下。拿二维网格类题目来说如果坐标范围变大比如 0 到 100000那么纯枚举就废了这时候你可能需要用到二维差分数组或者扫描线思想。比如“每个信号塔给一个矩形范围加权重最后求最大点”这个问题用二维差分可以在 O(塔数 网格点数) 的复杂度内解决。但 LeetCode 1620 的信号是按圆形范围衰减的差分就不好使了所以它把范围限制得这么小就是想引导你用暴力枚举。如果你刷到了类似的变体比如把信号公式改成max(0, power - distance)这种线性衰减其实求解思路完全一样还是枚举。但如果你把范围扩大到 10 的 6 次方那就得考虑用四叉树、KD 树这类空间索引的数据结构来做范围查询了。我自己在项目里做过类似的“基站覆盖热力图”需求当基站数量上万、网格精度到米级的时候暴力枚举根本跑不动最后用的是把地图划分成格子、每个基站只更新它附近的若干个格子再加一层空间索引才能实时出结果。LeetCode 大部分题都是给你一个理想化的、小规模的场景但它们背后往往映射着一个真实世界的工程问题。你在刷题时多问一句“如果数据规模变成十万、百万我这个解法还能用吗”会比多刷十道简单题更有收获。6. 实战复盘一次完整的 AC 过程为了让你更直观地看到这道题的解题全流程我以 Java 为例跑一个完整的流程从读题到提交通过。我拿到题之后先看数据范围。坐标范围是 0 到 50塔数量最大 50这两个条件一出来方案就定了双层循环枚举坐标内层循环遍历塔总计算量约 13 万这是一个任何语言都能秒过的量级。于是我先写了一个最简单、最不容易错的版本就是全网格扫描加跳出优化。写完第一版没过样例我认真检查了一遍才发现是 power 和 radius 搞混了。这里的 radius 是题目里给的接收半径参数而每个塔的第三个元素是发射功率。修正之后样例就过了。这是我这次刷题踩的最大一个坑比算法本身难多了。之后我把代码提交一次 AC运行时间大约是 1ms。这个成绩在 LeetCode 上已经是超过 100% 的 Java 提交了。随后我又试了用 Python 写一版同样的思路代码短了不少运行时间大约在 60ms 左右也完全能接受。这里给你贴一个 Python 的直观版本它比 Java 短很多适合理解思路class Solution: def bestCoordinate(self, towers: List[List[int]], radius: int) - List[int]: best_x best_y 0 best_signal -1 for x in range(51): for y in range(51): cur 0 for tx, ty, power in towers: d ((x - tx) ** 2 (y - ty) ** 2) ** 0.5 if d radius: cur int(power / (1 d)) if cur best_signal: best_signal cur best_x, best_y x, y return [best_x, best_y]看完这段代码你再回看整个解题过程会发现核心难点其实不在算法设计而在你能不能冷静地读完题、抓住数据范围、选对模拟策略。很多人说算法面试考的是思维但我越来越觉得考得更多的是一种工程判断力在约束条件明确的前提下选择最合适的暴力级别去解决问题。我在做完这道题之后顺手把它改成了“如果半径参数变成 0”的极端版本发现题目退化成“找 power 最大的塔本身的位置”这时候全场枚举依然能跑通只是白白算了 2601 个点。这也说明了一个道理如果一个题目的数据范围小到暴力都能过那你就放心写暴力但心里要清楚它的瓶颈在哪儿万一面试官追问一句“范围变大怎么办”你不至于哑口无言。 LeetCode 1620：网络信号最好的坐标——暴力枚举与信号强度计算解析
1. 先搞明白题目在问什么这道题你光看标题“网络信号最好的坐标”很容易以为是个贪心或者数学优化题实际上 LeetCode 1620 是一个标准的坐标几何枚举题。它给你一堆信号塔的坐标和发射功率让你在一个有限范围内找一个整数坐标点使得信号强度加起来最大。范围不大坐标上限是 50信号塔数量最多 50 个所以暴力枚举完全跑得动。核心公式其实就一句话对于每个整数坐标点遍历所有信号塔计算距离如果距离小于等于功率就把 ⌊功率 / (1 距离)⌋ 累加起来最后取信号强度最大的那个坐标。题目还加了一个条件如果多个点信号强度相同返回字典序最小的那个也就是 x 尽量小x 相同就 y 尽量小。我第一次看到这个题的时候第一反应是“这会不会要用三分搜索或者最近邻之类的玩意”毕竟网络信号、坐标最优点这种词很容易让人往计算几何方向联想。但看完数据范围就释然了坐标范围只有 0 到 50信号塔最多 50 个整个网格也就 51×51 个候选点每个点最多算 50 次距离总共 2601×50 13 万次操作这个量级连优化都懒得优化直接暴力就是最优解。这类题我在实际面试中也遇到过类似的变体比如“在网格上找信号覆盖最强的位置”或者把信号塔换成传感器、基站本质上都是同一个套路。它考察的其实不是你会不会高深的算法而是你愿不愿意老老实实把数据范围读完、敢不敢直接暴力。很多人在面试里一看到“最优坐标”这种字眼就开始设计复杂算法反而把简单题做复杂了这是很可惜的事。这道题还有个值得注意的点题目要求的是整数坐标点不是连续坐标。千万不要去想什么“对 x 求导等于 0”信号强度函数在这个定义下根本不可导因为它用的是一个固定功率除以距离加一的形式只在离散网格上成立。所以枚举就是最自然的解法。2. 信号强度计算的数学细节2.1 信号衰减公式到底怎么理解题目给的信号强度公式是signal floor(power / (1 distance))这里的 distance 是欧几里得距离也就是 sqrt((x - xi)² (y - yi)²)。注意这个公式里有个“1”它的作用是防止距离为 0 时除零同时也能让信号衰减得更平滑一些。实际通信工程里一般用自由空间路径损耗衰减跟距离的平方成正比但 LeetCode 这里为了简化直接用的线性衰减所以距离对信号的影响没那么剧烈。用这个公式看当你在信号塔正上方时distance 0信号强度就是 power相距 1 个单位时信号变成 power/2相距 3 个单位时变成 power/4。也就是说距离每增加“1 当前距离”这么多信号就减半一次。但因为我们用的是向下取整所以距离稍微大一点信号强度就可能降到 0。有一个很容易踩的坑题目说“如果距离大于 power则该塔信号为 0”这其实是为了避免出现“(distance 1) power 时 floor(power / (distance 1)) 自动变成 0”的情况但并不是说所有距离大于功率的塔信号都严格等于 0。比如 power 10distance 9那么 floor(10 / (9 1)) 1这时候虽然 distance power但信号强度已经是 1 了。如果 distance 20此时公式理论上算出来的 floor(10 / 21) 0也等于无效。所以判断条件用“distance power”还是“distance 1 power”会产生微小的差别虽然在多数情况下结果一致但为了防止边界问题最严谨的做法还是老老实实判断 distance power 才贡献信号。2.2 为什么枚举顺序能顺便解决字典序题目要求信号相同时取字典序最小的坐标即 x 越小越好x 相同时 y 越小越好。这个问题如果你单独去想可能还要写个比较器但在枚举框架里你只需要把 x 和 y 的循环顺序设计成从小到大然后用一个严格大于的判定条件去更新最大值就行了。也就是说初始化 bestX 0bestY 0bestSignal -1或者任何负数然后从 x 0 到 50y 0 到 50 依次遍历。计算当前点的信号强度 cur只有当 cur bestSignal 时才更新最优坐标。这样即使在后面遇到信号强度相同但字典序更大的点也不会覆盖之前已经记录的更小坐标天然就满足了题目要求。如果你脑子一抽把循环写成从大到小或者用了 来判断那最终返回的坐标就不一定是字典序最小的了。这个点看上去很细节但真在面试里写错了面试官一眼就能看出来你思考不周。最后提交报错的话排查起来也比较隐蔽因为它只在多个点信号相同的场景触发。3. 三种解法从暴力到优雅3.1 解法一全场枚举最稳的 0 思考实现第一种方案就是标准的全场枚举。先遍历一遍信号塔找到所有塔的坐标范围然后在这个范围内遍历所有整数点对每个点累加从所有塔收到的信号强度最后选出最大值。我直接用 Java 写了一个参考实现public int[] bestCoordinate(int[][] towers, int radius) { int minX 50, maxX 0, minY 50, maxY 0; for (int[] tower : towers) { minX Math.min(minX, tower[0]); maxX Math.max(maxX, tower[0]); minY Math.min(minY, tower[1]); maxY Math.max(maxY, tower[1]); } int bestX 0, bestY 0, bestSignal -1; for (int x 0; x 50; x) { for (int y 0; y 50; y) { int cur 0; for (int[] tower : towers) { int dx x - tower[0]; int dy y - tower[1]; double d Math.sqrt(dx * dx dy * dy); if (d radius) { cur (int) Math.floor(tower[2] / (1 d)); } } if (cur bestSignal) { bestSignal cur; bestX x; bestY y; } } } return new int[]{bestX, bestY}; }这里我没有真的去遍历信号塔的包围盒而是直接扫 0 到 50 的全网格。反正全网格也就 2601 个点每个点算 50 个欧氏距离性能完全没问题。这样代码还更短也不用多处理 towers 为空时的边界情况因为 towers 长度至少为 1。对每个点计算信号时先把 dx 和 dy 分别搞出来再算平方和的平方根最后用 Math.floor 做向下取整。注意这里如果你用强制类型转换(int)对于正数是向下取整对于负数则相当于向零取整但我们的信号值恒为 0 或正数所以两个写法等价。不过为了跟题目公式严格保持一致我建议用 Math.floor 处理避免以后把代码改成别的场景时出问题。3.2 解法二提前修剪遍历范围减少无用计算如果信号塔的坐标范围很小比如都集中在 [10, 20] 这个区间而你还在 0 到 50 的全网格上扫那就白白浪费了大量计算。更聪明一点的做法是先算出所有塔的 x 和 y 的边界再在这个包围盒里枚举这样能省掉很多明显不可能成为最优解的点。但有一个需要注意的地方信号最强的点不一定落在塔的包围盒内。比如两个塔分别在 (0,0) 和 (50,50)它们的包围盒是 [0,50]×[0,50]几乎覆盖全图所以不影响。但反过来想如果只有一个塔在 (0,0)另一个在 (0,10)最强的点固然在塔附近但也可能出现在 (0,1)、(0,2) 这种不在包围盒内的坐标上不对这些坐标在包围盒内。实际上完全有可能出现最强点在包围盒之外的反例所以边界剪枝必须保守——至少把包围盒向外扩展 radius 的距离才安全。编码上就是int minX 50, maxX 0, minY 50, maxY 0; for (int[] tower : towers) { minX Math.min(minX, tower[0]); maxX Math.max(maxX, tower[0]); minY Math.min(minY, tower[1]); maxY Math.max(maxY, tower[1]); } int startX Math.max(0, minX - radius); int endX Math.min(50, maxX radius); int startY Math.max(0, minY - radius); int endY Math.min(50, maxY radius); for (int x startX; x endX; x) { for (int y startY; y endY; y) { // 后续计算相同 } }这种优化的前提是你要理解如果某个点距离所有塔都超过了 radius那么它的信号强度一定是 0而所有塔所在的位置本身至少有一个塔在发射信号所以最优解一定在至少一个塔的 radius 范围内也就是在包围盒扩展 radius 后的矩形内。这个剪枝逻辑是严谨的不是拍脑袋拍出来的。实测下来如果信号塔坐标分布得很离散这种枚举范围剪枝可以节省 40% 甚至更多的无效坐标点计算。虽然 LeetCode 上这道题暴力也能过但写出这种优化起码说明你想问题更全面面试的时候是个加分项。3.3 解法三做一点距离公式的优化避免重复计算平方根平方根计算在计算机里是比较贵的操作虽然现代 CPU 对 sqrt 也有硬件指令但在 51×51×50 这个量级下其实无所谓。我这里的优化思路是先把信号塔的功率 radius 平方一下得到 maxDistSquare然后在判断距离是否有效时用 dxdx dydy maxDistSquare 替代 sqrt 再比较这样就省掉了每次计算距离时的开方操作。不过信号强度公式里还需要用到真实的距离值 1 d 作为分母所以这个方法只能省掉“判断是否在范围内”的那次开方真正计算信号强度时仍然需要开方。如果你实在想省掉所有开方操作就得对分母做变换但那样会引入浮点精度问题得不偿失。所以我在实现里采用了一种折中先快速判断是否在接收范围内如果不在就直接跳过省掉后续的 math floor 和除法如果在范围内再开方算真实信号强度。这样在多数塔分布稀疏的场景下能减少大量无效的乘除运算。写出来大概是这样的代码片段int maxDistSquare radius * radius; for (int[] tower : towers) { int dx x - tower[0]; int dy y - tower[1]; int distSquare dx * dx dy * dy; if (distSquare maxDistSquare) { continue; } double d Math.sqrt(distSquare); cur (int) Math.floor(tower[2] / (1 d)); }这是我在做题时比较偏爱的一种写法因为它在保持代码逻辑清晰的同时能明显减少无效计算实测性能也更好。如果你用 C你还可以用 int 类型全程计算把最后的比较条件转换成避免浮点误差的形式但这个对 Java 来说没必要毕竟这个题根本没要求你手写 sqrt。4. 常见问题与排查技巧实录4.1 字典序问题为什么我返回的坐标总是“错”的我在实际跑用例的时候第一版代码用的是“先算一个 max再扫描一遍等于 max 的坐标取最小”这种两遍式的写法看起来逻辑没毛病但就是会踩坑。原因很简单你如果第一遍扫描时用 来更新最优坐标那么循环顺序是 x 从 0 到 50、y 从 0 到 50那你最终拿到的反而是字典序最大的那个坐标。后来我改成一遍扫描加严格大于就把这个问题彻底解决了。如果你是在本地 IDE 里调试想肉眼验证是不是字典序的锅可以专门构造一个所有点信号都一样的用例比如只有一个信号塔功率 radius 0那整个网格上只有塔本身那个点的信号等于 power其他点全是 0这种情况下返回塔的位置就行看不出问题。要构造出有多个相同最优值的情况得让两个塔的覆盖范围对称这样在两个塔之间可能会出现信号值一样的点。4.2 半径处理radius 参数和塔的 power 是两回事这个题最容易让新手晕的点是radius 表示的是“塔的覆盖半径”就是距离超过这个值信号就衰减为 0power 是塔的发射功率决定近距离处的信号强度。两者在公式中承担的角色完全不一样。我在写题的时候第一时间就把它俩搞混了结果就是信号强度算出来乱七八糟一度以为是浮点精度问题。后来重新读题发现 distance radius 时不贡献信号而信号强度计算里的 power 是另一个量才把代码改对。建议你拿到题目后先把这两个变量用不同的命名区分开比如maxDistance和signalPower能减少很多低级错误。4.3 浮点误差引发的边界问题理论上如果两个坐标点的信号强度数学上相等但因为你用了 double 运算可能出现 5.999999999 和 6.000000001 这种微小差异。在这个题里由于信号强度公式最后要向下取整成 int所以这种误差反而会被“抹平”一部分但也不能完全排除边界情况。我见过有人把这个题的信号强度累加成 double最后再比较 double 大小结果因为微小的浮点误差导致返回了错误坐标。更稳妥的做法是每次计算单个塔的信号后立即取整到 int再累加到一个 int 变量里。这样整个过程都是整数运算完全避开浮点比较的不确定性。这也是我在参考实现里用cur (int) Math.floor(tower[2] / (1 d))而不是cur tower[2] / (1 d)再去比较的原因。4.4 全网格扫描 vs 包围盒扫描的取舍如果你看一些题解会发现不少人直接用 0 到 50 的全网格扫描也许会觉得那才是标准答案。但其实两者都可以通过只不过全网格扫描代码更短不容易漏点包围盒扫描则能节省一些计算量但必须注意扩展 radius否则可能漏掉最优解。我建议在比赛或面试中优先写全网格扫描因为简单、不可能错时间复杂度完全可接受。等你写完基本版本确认逻辑正确后再顺手加上包围盒优化这样即使优化写错了也不至于影响正确性。但如果你是先写优化版再翻车排查起来会比较痛苦因为你需要同时验证两件事一是枚举范围有没有漏点二是信号强度计算对不对。这里我整理了一个速查表方便你快速对照自己的代码问题所在症状可能原因解决办法强信号坐标答案和预期不符更新条件用了 覆盖了更小坐标改回严格大于循环从小到到输出坐标始终是 (0,0)初始化 bestSignal 0但存在信号更弱的点被跳过初始化为 -1范围很小但结果偏差包围盒没有扩展 radius对塔范围扩展 radius 后 clamp 到 [0,50]答案算出来差 1信号强度公式忘了向下取整或者用了四舍五入确认用 floor 处理大数据量超时每个坐标都手动调 sqrt 和 floor 太多次先判断 distSquare radius²再执行 sqrt4.5 关于“空塔”情况的特殊处理LeetCode 的约束里 towers.length 1所以严格来说不会遇到空数组。但如果你在扩展这个题或者面试官临时改题问“如果 towers 为空怎么办”那你需要在开头就判断一下如果 towers 长度为 0直接返回 {0, 0} 即可。这种防御性编程的习惯在实际项目里非常重要。我还遇到过一种特殊的输入所有塔的功率都是 0。这种情况下所有坐标的信号强度都是 0按照字典序最小的原则应该返回 (0, 0)。如果你的 bestSignal 初始化为 -1那么第一次循环到 (0,0) 就会把它更新成 bestSignal 0最终正确返回 (0,0)。所以初始化成 -1 是很有讲究的它能正确处理所有信号都是 0 的极端场景。5. 同类问题与思维拓展做完了 LeetCode 1620你会发现其实很多题都是这个套路的变体给你一堆有影响的点或范围在一个有限网格上评估所有位置最后找一个“最大/最小”的格点。比如热词里经常出现的 LeetCode 热门 100 题、周赛题以及 1273、073 这类编号题很多都能归到网格枚举、二维前缀和、差分数组这些框架下。拿二维网格类题目来说如果坐标范围变大比如 0 到 100000那么纯枚举就废了这时候你可能需要用到二维差分数组或者扫描线思想。比如“每个信号塔给一个矩形范围加权重最后求最大点”这个问题用二维差分可以在 O(塔数 网格点数) 的复杂度内解决。但 LeetCode 1620 的信号是按圆形范围衰减的差分就不好使了所以它把范围限制得这么小就是想引导你用暴力枚举。如果你刷到了类似的变体比如把信号公式改成max(0, power - distance)这种线性衰减其实求解思路完全一样还是枚举。但如果你把范围扩大到 10 的 6 次方那就得考虑用四叉树、KD 树这类空间索引的数据结构来做范围查询了。我自己在项目里做过类似的“基站覆盖热力图”需求当基站数量上万、网格精度到米级的时候暴力枚举根本跑不动最后用的是把地图划分成格子、每个基站只更新它附近的若干个格子再加一层空间索引才能实时出结果。LeetCode 大部分题都是给你一个理想化的、小规模的场景但它们背后往往映射着一个真实世界的工程问题。你在刷题时多问一句“如果数据规模变成十万、百万我这个解法还能用吗”会比多刷十道简单题更有收获。6. 实战复盘一次完整的 AC 过程为了让你更直观地看到这道题的解题全流程我以 Java 为例跑一个完整的流程从读题到提交通过。我拿到题之后先看数据范围。坐标范围是 0 到 50塔数量最大 50这两个条件一出来方案就定了双层循环枚举坐标内层循环遍历塔总计算量约 13 万这是一个任何语言都能秒过的量级。于是我先写了一个最简单、最不容易错的版本就是全网格扫描加跳出优化。写完第一版没过样例我认真检查了一遍才发现是 power 和 radius 搞混了。这里的 radius 是题目里给的接收半径参数而每个塔的第三个元素是发射功率。修正之后样例就过了。这是我这次刷题踩的最大一个坑比算法本身难多了。之后我把代码提交一次 AC运行时间大约是 1ms。这个成绩在 LeetCode 上已经是超过 100% 的 Java 提交了。随后我又试了用 Python 写一版同样的思路代码短了不少运行时间大约在 60ms 左右也完全能接受。这里给你贴一个 Python 的直观版本它比 Java 短很多适合理解思路class Solution: def bestCoordinate(self, towers: List[List[int]], radius: int) - List[int]: best_x best_y 0 best_signal -1 for x in range(51): for y in range(51): cur 0 for tx, ty, power in towers: d ((x - tx) ** 2 (y - ty) ** 2) ** 0.5 if d radius: cur int(power / (1 d)) if cur best_signal: best_signal cur best_x, best_y x, y return [best_x, best_y]看完这段代码你再回看整个解题过程会发现核心难点其实不在算法设计而在你能不能冷静地读完题、抓住数据范围、选对模拟策略。很多人说算法面试考的是思维但我越来越觉得考得更多的是一种工程判断力在约束条件明确的前提下选择最合适的暴力级别去解决问题。我在做完这道题之后顺手把它改成了“如果半径参数变成 0”的极端版本发现题目退化成“找 power 最大的塔本身的位置”这时候全场枚举依然能跑通只是白白算了 2601 个点。这也说明了一个道理如果一个题目的数据范围小到暴力都能过那你就放心写暴力但心里要清楚它的瓶颈在哪儿万一面试官追问一句“范围变大怎么办”你不至于哑口无言。