标签： 排序

目标

一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 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;
    }

}

性能

目标

现有 n 个机器人，编号从 1 开始，每个机器人包含在路线上的位置、健康度和移动方向。

给你下标从 0 开始的两个整数数组 positions、healths 和一个字符串 directions（directions[i] 为 'L' 表示 向左 或 'R' 表示 向右）。 positions 中的所有整数 互不相同 。

所有机器人以 相同速度 同时 沿给定方向在路线上移动。如果两个机器人移动到相同位置，则会发生 碰撞 。

如果两个机器人发生碰撞，则将 健康度较低 的机器人从路线中 移除 ，并且另一个机器人的健康度 减少 1 。幸存下来的机器人将会继续沿着与之前 相同 的方向前进。如果两个机器人的健康度相同，则将二者都从路线中移除。

请你确定全部碰撞后幸存下的所有机器人的 健康度 ，并按照原来机器人编号的顺序排列。即机器人 1 （如果幸存）的最终健康度，机器人 2 （如果幸存）的最终健康度等。 如果不存在幸存的机器人，则返回空数组。

在不再发生任何碰撞后，请你以数组形式，返回所有剩余机器人的健康度（按机器人输入中的编号顺序）。

注意：位置 positions 可能是乱序的。

示例 1：

输入：positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
输出：[2,17,9,15,10]
解释：在本例中不存在碰撞，因为所有机器人向同一方向移动。所以，从第一个机器人开始依序返回健康度，[2, 17, 9, 15, 10] 。

示例 2：

输入：positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
输出：[14]
解释：本例中发生 2 次碰撞。首先，机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。接下来，机器人 3 和机器人 4 将会发生碰撞，由于机器人 4 的健康度更小，则它会被移除，而机器人 3 的健康度变为 15 - 1 = 14 。仅剩机器人 3 ，所以返回 [14] 。

示例 3：

输入：positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL"
输出：[]
解释：机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。机器人 3 和机器人 4 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。所以返回空数组 [] 。

说明：

• 1 <= positions.length == healths.length == directions.length == n <= 10^5
• 1 <= positions[i], healths[i] <= 10^9
• directions[i] == 'L' 或 directions[i] == 'R'
• positions 中的所有值互不相同

思路

水平线上有 n 个机器人，第 i 个机器人的位置在 positions[i]，移动方向为 directions[i]，健康度为 healths[i]，每个机器人都以 相同的速度 沿着 directions[i] 方向移动，如果发生碰撞，健康度大的减一，小的归零，如果相等则一起归零，当健康度归零时，从水平线上移除。求剩余机器人的健康度，按照原来机器人的编号顺序输出。

类似于括号匹配，只不过是有条件的匹配。如果健康度相同可以抵消，否则健康度低的被移除，健康度高的减一。模拟碰撞过程即可。

代码

/**
 * @date 2026-04-01 9:01
 */
public class SurvivedRobotsHealths2751 {

    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        int[][] robots = new int[n][4];
        for (int i = 0; i < n; i++) {
            // 编号、位置、健康度、移动方向 1 向右，-1 向左
            robots[i] = new int[]{i + 1, positions[i], healths[i], directions.charAt(i) == 'R' ? 1 : -1};
        }
        Arrays.sort(robots, (a, b) -> a[1] - b[1]);
        Deque<int[]> q = new ArrayDeque<>();
        for (int[] robot : robots) {
            if (robot[3] == 1) {
                q.push(robot);
            } else {
                if (q.isEmpty()) {
                    q.push(robot);
                } else {
                    while (!q.isEmpty() && q.peek()[3] == 1) {
                        if (q.peek()[2] < robot[2]) {
                            q.poll();
                            robot[2]--;
                        } else if (q.peek()[2] == robot[2]) {
                            q.poll();
                            robot[2] = 0;
                            break;
                        } else {
                            q.peek()[2]--;
                            robot[2] = 0;
                            break;
                        }
                    }
                    if (robot[2] > 0) {
                        q.push(robot);
                    }
                }
            }
        }
        List<int[]> list = new ArrayList<>(q);
        list.sort((a, b) -> a[0] - b[0]);
        return list.stream().mapToInt(x -> x[2]).boxed().collect(Collectors.toList());
    }

}

性能