最好可到达的塔：边界条件与区间最值优化-北京尧图网络

双周赛第一题往往被当成热身题手速快的人咔咔两分钟就过了。但前几天这一场有一道叫“最好可到达的塔”的题让我在赛后复盘时想了很多。题目本身不复杂可是它的边界条件、输出规则和扩展空间都非常有代表性。如果你也习惯把这类题拿来练手那我建议你不要只满足于AC而是把这题从头到尾吃透因为这题的很多细节在真实项目和面试白板题里同样会踩到。先说题意数轴上有若干个塔每个塔有一个坐标和一个高度。你从某个起点出发沿着数轴移动移动总距离不能超过给定上限。现在要你找出你能到达的所有塔当中高度最高的那座塔的高度。如果一座塔都够不着就返回 -1。输入给的是塔的坐标数组、高度数组加上起点和可移动距离。看起来就是一个“遍历判断取最大”的操作但真上手写的时候还是有几个容易翻车的地方。1. 题目理解与核心思路拆解1.1 题意还原与关键点提取先把问题翻译成更严谨的数学描述。数轴上有 n 个塔第 i 个塔的位置是 x[i]高度是 h[i]。你的起点是 s最大移动距离是 d。所谓“能到达”指的是从 s 出发沿数轴最多走 d 的距离能走到某个塔所在的位置。由于是在一维数轴上移动因此到达塔 i 的充要条件就是|x[i] - s| d换句话说塔 i 的坐标必须落在区间 [s - d, s d] 内。在这个区间里所有塔都是可到达的我们要的是这些塔中最高的那个高度。这里有个很容易被忽略的点题目里的“移动”并没有要求你按照某种顺序走也没有中间的障碍物所以只要距离够得着就能直接到达。这跟二维平面里的“曼哈顿距离”或“欧几里得距离”问题不太一样一维场景下的可达性判断就是纯粹的绝对值比较。1.2 为什么不能直接排序思路选型很多人第一反应是把所有塔按高度从大到小排个序取最高的不就行了吗这个思路如果不等检查可达性就是错的。假设最高的塔在十万八千里外你根本走不到那这个塔再高也跟你没关系。正确顺序一定是“先过滤可达的塔再在这些塔里找最高”。所以核心解法其实就是两件事过滤取最大。最朴素的做法是遍历每个塔判断它是否在可达区间内如果在就用当前最高高度和它的高度比较更新答案。这个做法的时间复杂度是 O(n)空间复杂度是 O(1)对于第一题来说已经绰绰有余。但为什么我还要专门写一篇博文来聊它因为这个“简单”方案里埋着不少坑比如坐标类型、高度为负、答案初始化、重复位置以及如果扩展到多查询场景下如何优化都值得展开说说。2. 基础解法与实际操作2.1 暴力遍历的完整实现先给出最直接的实现。假设输入是整数数组 x 和 h起点是 s可移动距离是 d。Python版本def bestReachableTower(x, h, s, d): ans -1 for i in range(len(x)): if abs(x[i] - s) d: if h[i] ans: ans h[i] return ansC版本int bestReachableTower(vectorint x, vectorint h, int s, int d) { int ans -1; int n x.size(); for (int i 0; i n; i) { if (abs(x[i] - s) d) { ans max(ans, h[i]); } } return ans; }是不是特别简单如果到这里就收工那这篇文章就没有意义了。上面代码只是核心逻辑实际竞赛里你需要把输入输出处理好还要考虑数据范围。有一种常见写法是先把 ans 设为 INT_MIN 或一个大负数然后只更新可达的塔。但如果你把 ans 初始化为 0而塔的高度可能为负数那就会出问题所有可达塔的高度都是负数时答案是这些负数中最大的比如 -2而你的 ans 初始为 0最后会错误地返回 0。反过来如果所有塔都不可达你又希望区分“没有可达塔”和“可达但最高是负高度”这两种情况。更稳妥的做法是先用一个标志位记录是否找到了可达的塔或者让 ans 初始化为一个比所有可能高度都小的值。具体选多少要看数据范围。如果高度范围是 [-10^9, 10^9]那么初始化为 -10^18 或者用None/nullopt都行。我上面直接初始化为 -1相当于默认高度不会小于 -1如果题目没有规定高度必须非负这就是个隐患。2.2 边界条件与编码细节第一个边界是距离计算。很多人会写成x[i] - s d而忘了加绝对值这样只考虑了起点右侧的塔左侧的塔全部漏掉。绝对值本质上是把左右两个方向都覆盖了。如果你不想用abs也可以写成x[i] s - d x[i] s d等价而且有时因为分支预测和整数运算的关系反而更快。第二个边界是整数溢出。如果坐标范围到 1e9起点和距离也是 1e9那么x[i] - s的绝对值可能达到 2e9这还在 32 位带符号整数范围内。但如果你用s d判断可能溢出因为s d可能超过 int 的最大值。C 里最好统一用long long或者用abs((long long)x[i] - s)之类的写法。Python 没有这个问题但也不能掉以轻心因为列表长度很大时遍历性能也要考虑。第三个边界是塔的位置重复。如果两个塔在同一个坐标它们都落在可达区间内那就都得参与比较取高度更大的那个。这不会影响正确性但如果你在实现时用某个数据结构去重那就可能丢掉一个有效塔。第四个边界是 d 的取值。如果 d 是负数那一个塔都到不了应该返回 -1。绝大多数题目不会给负数但健壮的代码可以加个判断if (d 0) return -1;。有些平台的数据可能出得很阴间我们提前挡掉没坏处。3. 进阶优化与扩展思考3.1 从一次查询到多次查询离线处理与数据结构如果只是单次查询O(n) 遍历已经是最优。但如果我们把问题扩展成“有 q 个不同的起点 s每个查询给一个距离限制 d分别求可到达的最高塔”那每查询一次都做一遍 O(n) 遍历总复杂度 O(nq)当 n 和 q 都到 10^5 时就会超时。这时需要预处理。思路是把塔按坐标从小到大排序然后对于每个查询 (s, d)可达区间是 [s - d, s d]我们需要快速找到在这个坐标区间内所有塔的最大高度。这是一个典型的一维区间最大值查询问题可以直接用线段树或 Sparse Table 做 RMQ。具体步骤把塔按坐标 x 排序。建立一个线段树或 ST 表维护区间高度最大值。对于每个查询用二分查找找到左边界 l第一个坐标 s - d和右边界 r最后一个坐标 s d。查询 [l, r] 区间内的最大值如果 l r说明没有塔可达返回 -1。这样预处理建树 O(n)每次查询 O(log n)线段树或 O(1)ST 表总复杂度 O(n log n q log n)能轻松应付大数据。除此以外如果查询的起点 s 也是单调的还可以考虑滑动窗口单调队列的方式。因为 s 递增时窗口的左右边界也在单调右移我们可以离线排序查询然后用双端队列维护当前窗口内的最大值。这种技巧非常实用面试里问“滑动窗口最大值”其实就是同一套思路。不过针对这道题因为坐标区间不是固定长度的窗口需要把查询按 s 排序后用双指针维护所有可能落入区间的塔。这里有一个细节左指针要保证塔的坐标 s - d右指针要保证塔的坐标 s d左右指针的移动方向和时机需要仔细捋清楚否则容易把窗口维护错。3.2 从一维数轴到二维平面空间索引思路真实世界里“塔”往往是二维地图上的基站或信号塔这时候“可达”就不再是数轴上距离小于 d而可能是欧氏距离小于等于 d或者曼哈顿距离小于等于 d。问题变成给定 n 个二维坐标点 (x,y)每个点有权重 h每次查询给一个起点 (sx, sy) 和半径 d求圆内权重最大的点。一个直观做法是 KD 树。在建树时按坐标分维查询时剪枝平均复杂度可以做到 O(sqrt(n)) 级别。如果坐标范围有限且是整数还可以用二维差分前缀最大值来处理批量查询。另一种常用思路是栅格化把平面划分成网格每个网格预计算当前格子内权重最大值查询时覆盖圆形区域的网格都取最大值然后对边界网格做暴力检查。这一套在游戏服务器检测玩家周围怪物的时候特别常见典型的空间换时间。如果“塔”不是坐标点而是一个图上的节点边表示可达关系那么问题就变成从起点 s 出发在连通块内找到权值最大的节点。这个可以用 BFS/DFS 做连通块遍历每到一个节点就更新答案。如果边有方向且带权还要考虑最短路径限制那就要上 Dijkstra 之类的算法在松弛过程中维护最大权值。很多看似不同的题剥开外壳后核心就是“在一个可达集合里求最值”只是“可达”的定义不同罢了。4. 常见问题与排查技巧实录4.1 典型错误距离判断写错我见过很多人也包括我自己在写这道题的时候把绝对值给丢了。比如只用右边界判断if (x[i] - s d)结果左边坐标是 s - 100 的塔明明可以走到却被忽略。还有一种错误是用了平方距离没有开根号这在二维或更高维问题里尤其常见。如果题目用的是整数坐标你可能会为了避开浮点误差用dx*dx dy*dy d*d来判断欧氏距离这没错但前提是 d 本身也是整数而且不会溢出。一维场景下你就老老实实用绝对值别自己脑补成平方。4.2 数据范围与类型陷阱有次我在一个类似题上用 C 写坐标和距离都是 int 类型我直接写了s d作为右边界结果 s 1e9, d 1e9s d 溢出成了负数然后所有塔都不可达返回了 -1样例都过不了。排查了半天才发现是溢出。后来我养成了一个习惯涉及坐标加减的地方一律用long long或者在计算前先转换成long long。Python 虽然不担心溢出但如果用numpy之类的库默认整型也可能有精度问题所以要留意。4.3 高度为负时的初始值问题如果题目没有说明高度是非负整数那么把所有塔高度都看成普通整数即可。此时“没有可达塔”和“有可达但最高高度是负数”的返回结果是不同的。前者通常要求返回一个特殊值比如 -1后者应该返回那个负数本身。如果你把答案初始化为 0就会把负高度淹没掉。我用一个笨办法避免这个问题先用一个布尔变量标记是否找到了可达塔。伪代码如下found False ans -1 for i in range(n): if abs(x[i] - s) d: if not found or h[i] ans: ans h[i] found True if not found: return -1 return ans这样即使所有可达塔的高度都是负数也能正确返回最大的那个负数。如果你确定高度范围都是非负那直接ans 0也没有问题。但为了代码健壮我建议还是加上标志位成本很低。4.4 输出规则要看清题目如果要求输出“最高塔的高度”那简单直接返回高度值。但如果要求输出“最高的塔的编号”或“坐标”那就要小心多个塔同高度时题目可能要求返回编号最小/最大的那个。我的做法是保持“更新条件”为h[i] ans取高度严格大于当前最优值时才更新这样当两个塔高度相同最早出现的那个就是会被保留的答案。如果你想要编号最大的就把条件改成h[i] ans这样后出现的会覆盖先出现的。这一点千万不要想当然每个题的要求可能不一样。5. 赛后复盘的一点个人体会这道题本身并不难但它像一面镜子能照出你对边界条件的敏感度。我在实际写代码时最后用了long long存储坐标差值加了found标志还特意把d 0的情况挡掉才在提交时一遍过。挺多人在简单题上掉分不是因为不会算法而是因为太自信不看数据范围不检查负数不读输出规则。这些习惯带到真实项目里更危险。最后再分享一个小技巧如果你在比赛里遇到这种“求某个范围内的最值”的题不论范围是一维区间也好二维图形也罢第一件事永远是“先把可达性判清楚再谈最优”。很多人一看到“最好”“最大”“最高”就开始排序、贪心结果忽略了可达性的约束直接掉进陷阱。把这句话记在脑子里能少走很多弯路。

最好可到达的塔：边界条件与区间最值优化

相关推荐

Hystrix超时机制原理与调优实战：从默认1秒到合理设置

陕西GogoAI自助健身小程序团购套餐模块开发

基于MCP协议构建3D场景AI控制服务：从工具定义到批量操作实战

更多资讯

多谐振荡器从仿真到实物：Multivibrator.zip 设计避坑指南

HotSpot JVM核心机制：内存布局、垃圾回收与JIT编译调优

堆排序算法实验报告：Java实现、复杂度分析与避坑指南

ArcGIS API for JavaScript本地部署到IIS：从下载到dojoConfig全流程

Windows注册表原理与实战：查看、修改、备份、避坑全指南

WuKongIM 移除旧版 v1 Runtime：Legacy 代码树清理实施计划与落地源码验证

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？