目标
一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 robots ，distance 和 walls：
- robots[i] 是第 i 个机器人的位置。
- distance[i] 是第 i 个机器人的子弹可以行进的 最大 距离。
- walls[j] 是第 j 堵墙的位置。
每个机器人有 一颗 子弹，可以向左或向右发射，最远距离为 distance[i] 米。
子弹会摧毁其射程内路径上的每一堵墙。机器人是固定的障碍物：如果子弹在到达墙壁前击中另一个机器人，它会 立即 在该机器人处停止，无法继续前进。
返回机器人可以摧毁墙壁的 最大 数量。
注意：
- 墙壁和机器人可能在同一位置；该位置的墙壁可以被该位置的机器人摧毁。
- 机器人不会被子弹摧毁。
示例 1:
输入: robots = [4], distance = [3], walls = [1,10]
输出: 1
解释:
robots[0] = 4 向 左 发射，distance[0] = 3，覆盖范围 [1, 4]，摧毁了 walls[0] = 1。
因此，答案是 1。
示例 2:
输入: robots = [10,2], distance = [5,1], walls = [5,2,7]
输出: 3
解释:
robots[0] = 10 向 左 发射，distance[0] = 5，覆盖范围 [5, 10]，摧毁了 walls[0] = 5 和 walls[2] = 7。
robots[1] = 2 向 左 发射，distance[1] = 1，覆盖范围 [1, 2]，摧毁了 walls[1] = 2。
因此，答案是 3。
示例 3:
输入: robots = [1,2], distance = [100,1], walls = [10]
输出: 0
解释:
在这个例子中，只有 robots[0] 能够到达墙壁，但它向 右 的射击被 robots[1] 挡住了，因此答案是 0。
说明:
- 1 <= robots.length == distance.length <= 10^5
- 1 <= walls.length <= 10^5
- 1 <= robots[i], walls[j] <= 10^9
- 1 <= distance[i] <= 10^5
- robots 中的所有值都是 互不相同 的
- walls 中的所有值都是 互不相同 的
思路
无限长的直线上分布着一些机器人（位于 robots[i]）和墙壁 （位于 walls[j]），机器人可以向左或向右发射一枚子弹，位于 robots[i] 的机器人发射的子弹最多可以行进 distance[i]。子弹会摧毁其射程内路径上的每一堵墙，子弹不能摧毁或穿过机器人，求摧毁墙的最大数目。所有机器人的位置都是互不相同的，所有墙的位置也是互不相同的。
根据机器人的位置排序，考虑相邻机器人可以摧毁的墙的数目。定义 dp[i][k] 表示前 i 个机器人摧毁墙的最大数目，且第 i 个机器人朝 k 发射子弹，k = 0 表示向左， k = 1 表示向右。walls(from, to) 表示区间 [from, to] 内的墙的个数。
-
dp[i][0] = max(dp[i - 1][0] + walls(max(prev + 1, cur - dcur), cur), dp[i - 1][1] + walls(max(prev + dprev + 1, cur - dcur), cur))
-
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + walls(cur, min(cur + dcur, next - 1))
-
当前机器人向左射，需要考虑前一个机器人的射击方向，如果前一个机器人也向左射，只需考虑区间 [max(prev + 1, cur - dcur), cur] 中墙的个数，如果向右射则需要考虑 [max(prev + dprev + 1, cur - dcur), cur] 中墙的个数。其中 dcur 表示位于 cur 的机器人的射击距离，dprev 表示位于 prev 机器人的射击距离。
-
当前机器人向右射，无需考虑前一个机器人的射击方向，取二者最大的即可，当前机器人向右射的范围是 [cur, min(cur + dcur, next - 1)]，注意特殊处理最后一个机器人，没有 next 时取 Integer.MAX_VALUE。
剩下的问题是如何快速获取区间内墙的数量，由于不涉及更新，可以直接二分获得上下界。
代码
/**
* @date 2026-04-03 10:14
*/
public class MaxWalls3661 {
public int maxWalls(int[] robots, int[] distance, int[] walls) {
Arrays.sort(walls);
int n = robots.length;
Integer[] index = new Integer[n];
Arrays.setAll(index, i -> i);
Arrays.sort(index, (a, b) -> robots[a] - robots[b]);
int[][] dp = new int[n][2];
Integer first = index[0];
dp[0][0] = getWalls(walls, robots[first] - distance[first], robots[first]);
dp[0][1] = getWalls(walls, robots[first], Math.min(robots[first] + distance[first], n > 1 ? robots[index[1]] - 1 : Integer.MAX_VALUE));
for (int i = 1; i < n; i++) {
Integer cur = index[i];
Integer prev = index[i - 1];
dp[i][0] = Math.max(dp[i - 1][0] + getWalls(walls, Math.max(robots[prev] + 1, robots[cur] - distance[cur]), robots[cur]),
dp[i - 1][1] + getWalls(walls, Math.max(robots[cur] - distance[cur], robots[prev] + distance[prev] + 1), robots[cur]));
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]) + getWalls(walls, robots[cur], Math.min(robots[cur] + distance[cur], i < n - 1 ? robots[index[i + 1]] - 1 : Integer.MAX_VALUE));
}
return Math.max(dp[n - 1][0], dp[n - 1][1]);
}
/**
* 获取 [from, to] 之间的墙的数量
*/
public int getWalls(int[] walls, int from, int to) {
int r = upperBound(walls, to);
int l = lowerBound(walls, from);
if (r < l) {
return 0;
}
return r - l + 1;
}
/**
* 返回 <= target 的最大下标
*/
public int upperBound(int[] walls, int target) {
int l = 0, r = walls.length - 1;
int m = l + (r - l) / 2;
while (l <= r) {
if (walls[m] <= target) {
l = m + 1;
} else {
r = m - 1;
}
m = l + (r - l) / 2;
}
return r;
}
/**
* 返回 >= target 的最小下标
*/
public int lowerBound(int[] walls, int target) {
int l = 0, r = walls.length - 1;
int m = l + (r - l) / 2;
while (l <= r) {
if (walls[m] >= target) {
r = m - 1;
} else {
l = m + 1;
}
m = l + (r - l) / 2;
}
return l;
}
}
性能
