3661. 可以被机器人摧毁的最大墙壁数目 详细技术解析（动态规划解法）

3661. 可以被机器人摧毁的最大墙壁数目 详细技术解析动态规划解法本文针对「3661. 可以被机器人摧毁的最大墙壁数目」问题采用动态规划思路进行详细解析从问题描述、核心规则、思路推导、预处理细节到代码实现、示例验证逐步拆解解题逻辑适用于算法面试、刷题进阶及工程实践参考兼顾专业性与易懂性。一、问题描述在一条无限长的直线上分布着一些机器人和墙壁。给定三个整数数组robots[i]第 i 个机器人的位置。distance[i]第 i 个机器人的子弹可以行进的最大距离。walls[j]第 j 堵墙的位置。核心规则每个机器人有一颗子弹可向左或向右发射射程不超过distance[i]米。子弹会摧毁其射程内路径上的每一堵墙。机器人是固定障碍物子弹在到达墙壁前击中其他机器人会立即停止无法继续前进。墙壁和机器人可能在同一位置该位置的墙壁可被该机器人摧毁。机器人不会被子弹摧毁。要求返回机器人可以摧毁墙壁的最大数量。二、解题思路动态规划核心本题的核心难点在于「机器人遮挡效应」和「射击方向的最优选择」传统贪心策略虽能解决部分场景但无法处理相邻机器人射击范围重叠的最优决策问题。因此采用「动态规划」思路通过状态定义捕捉每个机器人的射击决策结合预处理的覆盖范围实现全局最优解。2.1 核心规则拆解理解阻挡机制子弹从机器人位置出发沿直线向左/向右飞行遇到其他机器人立即停止无法继续前进墙壁不阻挡子弹仅被子弹摧毁。每个机器人的有效射击范围受两个因素限制自身最大射程distance[i]、对应方向上最近的机器人若存在。机器人自身位置的墙壁只有发射子弹任意方向才能摧毁不发射则无法摧毁。2.2 区间定义与分段思想第一步对机器人按位置排序记排序后机器人位置为p[i]射程为d[i]此时整条直线被机器人位置分割成n1个独立段n 为机器人数量段 0(-∞, p[0])最左侧机器人左侧区域段 i1 ≤ i ≤ n-1(p[i-1], p[i])第 i-1 个与第 i 个机器人之间的区域段 n(p[n-1], ∞)最右侧机器人右侧区域关键结论每个机器人的子弹仅能影响其左右两个相邻段向左发射影响左侧段向右发射影响右侧段。每个段内的墙壁仅能被其左右两个机器人的子弹覆盖段 0 仅能被机器人 0 向左发射覆盖段 n 仅能被机器人 n-1 向右发射覆盖。段与段之间相互独立仅通过机器人的射击决策是否发射、发射方向产生耦合为动态规划状态设计提供基础。2.3 有效射击区间定义对排序后的第 i 个机器人定义其左右两侧最近机器人若存在左侧最近机器人位置L p[i-1]i 0否则L -∞用极小值替代。右侧最近机器人位置R p[i1]i n-1否则R ∞用极大值替代。基于遮挡规则有效射击区间仅包含墙壁不包含机器人自身位置定义如下向左发射有效覆盖区间为[max(p[i]-d[i], L1), p[i]-1]即子弹能到达的最左位置与自身位置之间的墙壁。向右发射有效覆盖区间为[p[i]1, min(p[i]d[i], R-1)]即自身位置与子弹能到达的最右位置之间的墙壁。补充机器人自身位置的墙壁若存在单独记为「自收益」只要发射子弹任意方向即可摧毁。2.4 动态规划状态设计核心思路用动态规划捕捉每个机器人的射击状态记录前 i1 个机器人的最大摧毁数结合相邻机器人的决策耦合实现全局最优。2.4.1 预处理变量定义self_wall[i]第 i 个机器人位置上是否有墙壁有则为 1否则为 0自收益。left_range[i]第 i 个机器人向左发射时覆盖其左侧段内墙壁的「全局索引区间」左闭右开无覆盖则为 None。right_range[i]第 i 个机器人向右发射时覆盖其右侧段内墙壁的「全局索引区间」左闭右开无覆盖则为 None。both_cover[i]段 i1第 i 个与第 i1 个机器人之间中机器人 i 向右发射、机器人 i1 向左发射时两者覆盖墙壁的并集数量避免重复计数。2.4.2 DP状态定义定义dp[i][s]表示考虑前 i1 个机器人0~i且第 i 个机器人的射击状态为s时能摧毁的最大墙壁数目。状态s取值及含义s0不发射子弹无任何覆盖自收益为 0。s1向左发射子弹获得自收益 左侧段覆盖收益。s2向右发射子弹获得自收益 右侧段覆盖收益右侧段收益需结合下一个机器人状态。2.4.3 状态初始化i0第一个机器人dp[0][0] 0不发射无收益。dp[0][1] self_wall[0] left_range[0] 的区间长度无覆盖则为 0向左发射获得自收益 左侧段覆盖收益。dp[0][2] self_wall[0]向右发射仅获得自收益右侧段收益需后续结合下一个机器人。2.4.4 状态转移i 从 0 到 n-2枚举当前机器人 i 的状态s和下一个机器人 i1 的状态t计算转移后的最大收益核心是计算「新增收益」自收益 段收益自收益add机器人 i1 发射子弹t≠0则获得self_wall[i1]否则为 0。段收益seg_gain对应段 i1机器人 i 与 i1 之间的收益分4种情况若 s2机器人 i 向右且 t1机器人 i1 向左段收益为both_cover[i]并集覆盖避免重复。若 s2 且 t≠1段收益为right_range[i]的区间长度仅机器人 i 向右覆盖。若 s≠2 且 t1段收益为left_range[i1]的区间长度仅机器人 i1 向左覆盖。否则段收益为 0无机器人覆盖该段。转移公式dp[i1][t] max(dp[i1][t], dp[i][s] add seg_gain)2.4.5 最终答案计算最后一个机器人in-1的右侧段段 n仅能被其向右发射覆盖因此需补充该段收益对每个状态 s0、1、2计算val dp[n-1][s] right_range[n-1] 的区间长度s2 且有覆盖则加否则为 0。最终答案为所有 val 中的最大值。2.5 预处理细节关键优化由于机器人和墙壁数量均可达 1e5需通过「排序 二分查找」优化预处理效率核心步骤排序机器人绑定位置和射程、排序墙壁便于后续二分查找。计算每个段的墙壁索引范围左闭右开通过 bisect 找到每个段在排序墙壁数组中的起始和结束索引快速定位段内墙壁。计算每个机器人的 left_range 和 right_range通过二分查找确定有效射击区间在排序墙壁数组中的索引再与对应段的索引范围取交集得到实际覆盖的墙壁索引区间。计算 both_cover对相邻机器人的 right_range 和 left_range计算两者索引区间的并集长度避免重复计数。三、算法复杂度分析排序复杂度O((nm) log(nm))其中 n 为机器人数量m 为墙壁数量排序机器人和墙壁。预处理复杂度O((nm) log m)每个二分查找操作时间为O(log m)预处理步骤共 O(nm) 次二分。动态规划复杂度O(9n) O(n)每个机器人有 3 种状态状态转移时枚举 3×39 种组合共 n 个机器人。总复杂度O((nm) log(nm))可轻松满足 1e5 规模的数据要求无超时风险。四、完整代码实现Python代码严格遵循上述思路注释清晰可直接复制运行适配题目所有测试用例兼顾可读性与效率。fromtypingimportListimportbisectclassSolution:defmaxWalls(self,robots:List[int],distance:List[int],walls:List[int])-int:# 1. 按位置排序机器人绑定位置和射程nlen(robots)robot_datasorted(zip(robots,distance))pos[pforp,_inrobot_data]# 排序后的机器人位置dist[dfor_,dinrobot_data]# 排序后的机器人射程# 2. 排序墙壁并用集合快速判断机器人位置是否有墙壁自收益walls_sortedsorted(walls)mlen(walls_sorted)wall_setset(walls)# 3. 预处理每个机器人自身位置的墙壁自收益self_wall[1ifpinwall_setelse0forpinpos]# 4. 预处理每个段的墙壁索引范围左闭右开共n1个段seg_start[0]*(n1)# 段i的起始索引墙壁数组中seg_end[0]*(n1)# 段i的结束索引墙壁数组中# 段0: (-inf, pos[0])墙壁索引范围[0, bisect_left(walls_sorted, pos[0])]seg_end[0]bisect.bisect_left(walls_sorted,pos[0])# 中间段i1in-1: (pos[i-1], pos[i])foriinrange(n-1):seg_start[i1]bisect.bisect_right(walls_sorted,pos[i])seg_end[i1]bisect.bisect_left(walls_sorted,pos[i1])# 段n: (pos[n-1], inf)墙壁索引范围[bisect_right(walls_sorted, pos[n-1]), m]seg_start[n]bisect.bisect_right(walls_sorted,pos[n-1])seg_end[n]m# 5. 预处理每个机器人的左/右覆盖索引区间左闭右开left_range[None]*n# 向左发射覆盖的墙壁索引区间right_range[None]*n# 向右发射覆盖的墙壁索引区间foriinrange(n):ppos[i]ddist[i]# 计算向左发射的有效覆盖区间ifi0:Lpos[i-1]1# 左侧最近机器人位置1避免击中该机器人else:L-10**18# 左侧无机器人取极小值负无穷left_boundmax(p-d,L)# 向左能到达的最左边界# 有效区间需满足left_bound p-1否则无墙壁可覆盖ifleft_boundp-1:# 二分查找墙壁数组中[left_bound, p-1]的索引范围lbisect.bisect_left(walls_sorted,left_bound)rbisect.bisect_right(walls_sorted,p-1)# 与段i左侧段的索引范围取交集得到实际覆盖区间seg_lseg_start[i]seg_rseg_end[i]iflrandlseg_randrseg_l:startmax(l,seg_l)endmin(r,seg_r)ifstartend:left_range[i](start,end)# 计算向右发射的有效覆盖区间ifin-1:Rpos[i1]-1# 右侧最近机器人位置-1避免击中该机器人else:R10**18# 右侧无机器人取极大值正无穷right_boundmin(pd,R)# 向右能到达的最右边界# 有效区间需满足right_bound p1否则无墙壁可覆盖ifright_boundp1:# 二分查找墙壁数组中[p1, right_bound]的索引范围lbisect.bisect_left(walls_sorted,p1)rbisect.bisect_right(walls_sorted,right_bound)# 与段i1右侧段的索引范围取交集得到实际覆盖区间seg_lseg_start[i1]seg_rseg_end[i1]iflrandlseg_randrseg_l:startmax(l,seg_l)endmin(r,seg_r)ifstartend:right_range[i](start,end)# 6. 预处理both_cover[i]段i1的并集覆盖数量both_cover[0]*(n-1)foriinrange(n-1):# 机器人i向右覆盖right_range[i]和机器人i1向左覆盖left_range[i1]rightright_range[i]leftleft_range[i1]ifleftisNoneandrightisNone:cnt0elifleftisNone:cntright[1]-right[0]elifrightisNone:cntleft[1]-left[0]else:# 计算两个区间的并集长度 两个区间长度和 - 交集长度l1,r1right l2,r2left total(r1-l1)(r2-l2)overlapmax(0,min(r1,r2)-max(l1,l2))cnttotal-overlap both_cover[i]cnt# 7. 动态规划DP求解INF_NEG-10**9# 负无穷用于初始化不可达状态dp[[INF_NEG]*3for_inrange(n)]# dp[i][s]前i1个机器人状态s的最大摧毁数# 初始化第一个机器人i0dp[0][0]0# 不发射# 向左发射自收益 左侧覆盖收益left_cntleft_range[0][1]-left_range[0][0]ifleft_range[0]else0dp[0][1]self_wall[0]left_cnt# 向右发射仅自收益右侧覆盖收益后续转移dp[0][2]self_wall[0]# 状态转移遍历前n-1个机器人更新i1的状态foriinrange(n-1):forsinrange(3):# 当前机器人i的状态sifdp[i][s]INF_NEG:continue# 不可达状态跳过fortinrange(3):# 下一个机器人i1的状态t# 计算自收益i1发射则有自收益否则无addself_wall[i1]ift!0else0# 计算段收益段i1的收益seg_gain0ifs2andt1:seg_gainboth_cover[i]elifs2:seg_gainright_range[i][1]-right_range[i][0]ifright_range[i]else0elift1:seg_gainleft_range[i1][1]-left_range[i1][0]ifleft_range[i1]else0# 更新dp[i1][t]为最大值new_valdp[i][s]addseg_gainifnew_valdp[i1][t]:dp[i1][t]new_val# 8. 计算最终答案补充最后一个机器人右侧段段n的收益ans0forsinrange(3):valdp[n-1][s]# 若最后一个机器人向右发射补充右侧段段n的收益ifs2andright_range[n-1]:valright_range[n-1][1]-right_range[n-1][0]ifvalans:ansvalreturnans五、示例验证全覆盖测试用例以下三个示例均为题目给出的典型场景代码运行结果与预期一致验证了解题思路和代码的正确性。5.1 示例1输入robots [4], distance [3], walls [1,10]输出1解析机器人排序后pos [4]dist [3]。自收益self_wall[0] 04不在walls中。向左发射有效区间 [max(4-3, -∞), 3] [1,3]覆盖墙壁1left_range[0] (0,1)walls_sorted [1,10]收益1。向右发射有效区间 [5, min(7, ∞)] [5,7]无墙壁收益0。DP初始化dp[0][1] 011dp[0][2]0dp[0][0]0。最终答案max(10, 00, 0) 1符合预期。5.2 示例2输入robots [10,2], distance [5,1], walls [5,2,7]输出3解析机器人排序后pos [2,10]dist [1,5]。自收益self_wall[0] 12在walls中self_wall[1] 010不在walls中。机器人0pos2向左发射有效区间 [max(1, -∞), 1] [1,1]无墙壁向右发射有效区间 [3, min(3, 9)] [3,3]无墙壁。机器人1pos10向左发射有效区间 [max(5, 3), 9] [5,9]覆盖墙壁5、7left_range[1] (1,3)walls_sorted [2,5,7]收益2向右发射无墙壁。both_cover[0]机器人0向右无覆盖和机器人1向左覆盖2个并集收益2。DP转移后最终收益机器人0向左10 机器人1向左02 3符合预期。5.3 示例3输入robots [1,2], distance [100,1], walls [10]输出0解析机器人排序后pos [1,2]dist [100,1]。自收益self_wall[0] 0self_wall[1] 01、2均不在walls中。机器人0向右发射有效区间 [2, min(101, 1)] [2,1]无效向左发射无墙壁。机器人1向左发射有效区间 [max(1, 2), 1] [2,1]无效向右发射有效区间 [3,3]无墙壁。所有状态收益均为0最终答案0符合预期。六、常见问题与注意事项6.1 常见错误点忽略遮挡规则未考虑相邻机器人对射击范围的遮挡直接按最大射程计算导致覆盖区间错误。重复计数相邻机器人射击范围重叠时未计算并集导致同一段墙壁被重复统计。自收益遗漏机器人自身位置的墙壁未判断是否发射子弹就计入收益或发射后未计入。二分查找边界错误混淆 bisect_left 和 bisect_right导致段内墙壁索引范围计算偏差。6.2 优化建议内存优化若墙壁数量极大可省略 wall_set直接用 bisect 二分查找判断机器人位置是否有墙壁时间复杂度不变空间复杂度从 O(m) 降至 O(1)。代码简化可将「二分查找计算区间」「并集长度计算」封装为独立函数提升代码可读性和可维护性。效率优化对于 n1 的场景单个机器人可直接单独处理跳过 DP 流程提升运行速度边际优化不影响整体复杂度。七、总结本题的核心是「分段思想 动态规划」通过分段将复杂的全局问题拆解为独立的局部问题再通过动态规划捕捉机器人射击决策的耦合关系实现全局最优。关键在于正确理解遮挡规则精准定义有效射击区间避免因遮挡导致的覆盖范围错误。合理设计 DP 状态将机器人的射击决策不发射、向左、向右转化为可量化的状态通过状态转移实现收益最大化。利用「排序 二分查找」优化预处理效率确保算法能应对 1e5 规模的数据。该解题思路可迁移到类似的「区间覆盖 决策优化」问题如资源分配、任务调度具有较强的通用性。代码经过严格测试可直接用于算法面试或工程实践同时也为后续类似问题的求解提供了清晰的思路框架。