2026-01-26：可以被机器人摧毁的最大墙壁数目。用go语言，在一条无限延伸的直线上，分布着若干机器人和若干堵墙。给定三个整数数组：表示机器人位置的 robots、表示每个机器人射程的 distance、以及表示墙位置的 walls。

要求说明如下：

• 第 i 个机器人位于位置 robots[i]，它只有一发子弹，可向左或向右发射，射程不超过 distance[i]。

• 子弹沿直线前进，沿途遇到的墙都会被摧毁，但如果子弹在抵达某面墙之前撞上了另一个机器人，它会在该机器人处停止，不能再继续前进。

• 机器人和墙可以处在同一位置；在该点的墙可以被该位置的机器人摧毁。机器人本身不会被子弹击毁。

目标是确定在所有机器人各自选择发射方向的最佳安排下，最多能摧毁多少面墙，并返回这一最大值。

1 <= robots.length == distance.length <= 100000。

1 <= walls.length <= 100000。

1 <= robots[i], walls[j] <= 1000000000。

1 <= distance[i] <= 100000。

robots 中的所有值都是 互不相同 的。

walls 中的所有值都是 互不相同 的。

输入: 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。

题目来自力扣3661。

算法步骤详解

1. 初始化与预处理

• 首先获取机器人数量 n 和墙的数量 m。
• 创建一个 pair 结构体数组 a，长度为 n+2，用于存储每个机器人的位置和射程。多出的两个位置用于设置哨兵。
• 将输入的机器人位置和射程填充到 a 数组的前 n 个元素中。
• 设置两个哨兵：
  • 第一个哨兵在索引0位置，其位置被隐式视为负无穷（通过排序后位于最左端）。
  • 第二个哨兵在索引 n+1 位置，位置设为 math.MaxInt（正无穷）。
• 对机器人数组 a 按位置进行升序排序，确保机器人从左到右排列。
• 对墙的位置数组 walls 进行升序排序，这是后续使用双指针技术的基础。

2. 变量定义与初始化

• f0, f1: 动态规划状态变量，表示到当前机器人为止，采用不同射击策略能摧毁的最大墙数。
• left, cur, right0, right1: 双指针，用于快速定位墙数组中满足特定条件的区间。
• 初始化这些指针都为0，表示从墙数组的起始位置开始扫描。

3. 主循环处理每个机器人

对排序后的每个机器人（从第1个到第n个）进行如下处理：

3.1 计算向左射击的摧毁范围

• 向左射击的有效范围是 [leftX, p.x]，其中：
  • leftX = max(p.x - p.d, a[i-1].x + 1)：确保子弹不会打到左边相邻的机器人。
• 使用 left 指针找到第一个大于等于 leftX 的墙的位置。
• 使用 cur 指针找到第一个大于等于 p.x 的墙的位置。
• cur1 作为 cur 的临时备份，用于记录当前机器人位置之前的墙的索引。
• 如果当前位置 p.x 恰好有墙，cur 指针需要跳过这面墙。
• 计算向左射击能摧毁的墙数：f0 + (cur - left)。

3.2 处理向右射击的两种情况

情况一：右边机器人向左射击

• 确定当前机器人向右射击的有效范围 [p.x, rightX]，其中：
  • rightX = min(p.x + p.d, q.x - q.d - 1)：确保与右边机器人向左射击的覆盖范围不重叠。
• 使用 right0 指针找到第一个大于 rightX 的墙的位置。
• 更新状态 f0 = max(leftRes, f1 + (right0 - cur1))。

情况二：右边机器人向右射击

• 确定当前机器人向右射击的有效范围 [p.x, rightX]，其中：
  • rightX = min(p.x + p.d, q.x - 1)：确保子弹不会打到右边相邻的机器人。
• 使用 right1 指针找到第一个大于 rightX 的墙的位置。
• 更新状态 f1 = max(leftRes, f1 + (right1 - cur1))。

4. 双指针技术的运用

• 所有指针 (left, cur, right0, right1) 在整个算法过程中只向前移动，不会回退。
• 这种设计确保了每个墙最多被每个指针访问一次，实现了高效的范围查询。

5. 结果返回

• 循环结束后，返回 f1 作为最终结果，表示所有机器人都处理完后能摧毁的最大墙数。

复杂度分析

时间复杂度

• 排序操作：对机器人排序时间复杂度为 O(n log n)，对墙排序时间复杂度为 O(m log m)。
• 主循环：虽然循环嵌套了多个while循环，但由于使用了双指针技术，所有指针总共移动次数不超过 O(m)。
• 总体时间复杂度：O(n log n + m log m)，主要由排序步骤决定。

空间复杂度

• 额外数组：创建了大小为 n+2 的 pair 数组，空间为 O(n)。
• 变量存储：使用了常数个指针变量和状态变量。
• 总体空间复杂度：O(n)（不考虑输入数据本身的存储）。

这个算法通过巧妙的排序和双指针技术，高效地解决了机器人射击方向的优化问题，在保证正确性的同时达到了较好的时间复杂度。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
	"slices"
)

func maxWalls(robots []int, distance []int, walls []int) int {
	n, m := len(robots), len(walls)
	type pair struct{ x, d int }
	a := make([]pair, n+2)
	for i, x := range robots {
		a[i] = pair{x, distance[i]}
	}
	a[n+1].x = math.MaxInt // 哨兵
	slices.SortFunc(a, func(a, b pair) int { return a.x - b.x })
	slices.Sort(walls)

	var f0, f1, left, cur, right0, right1 int
	for i := 1; i <= n; i++ {
		p := a[i]

		// 往左射，墙的坐标范围为 [leftX, p.x]
		leftX := max(p.x-p.d, a[i-1].x+1) // +1 表示不能射到左边那个机器人
		for left < m && walls[left] < leftX {
			left++
		}
		for cur < m && walls[cur] < p.x {
			cur++
		}
		cur1 := cur
		if cur < m && walls[cur] == p.x {
			cur++
		}
		leftRes := f0 + cur - left // 下标在 [left, cur-1] 中的墙都能摧毁

		// 往右射，右边那个机器人往左射，墙的坐标范围为 [p.x, rightX]
		q := a[i+1]
		rightX := min(p.x+p.d, q.x-q.d-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
		for right0 < m && walls[right0] <= rightX {
			right0++
		}
		f0 = max(leftRes, f1+right0-cur1) // 下标在 [cur1, right0-1] 中的墙都能摧毁

		// 往右射，右边那个机器人往右射，墙的坐标范围为 [p.x, rightX]
		rightX = min(p.x+p.d, q.x-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
		for right1 < m && walls[right1] <= rightX {
			right1++
		}
		f1 = max(leftRes, f1+right1-cur1) // 下标在 [cur1, right0-1] 中的墙都能摧毁
	}
	return f1
}

func main() {
	robots := []int{10, 2}
	distance := []int{5, 1}
	walls := []int{5, 2, 7}
	result := maxWalls(robots, distance, walls)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List
import math

def maxWalls(robots: List[int], distance: List[int], walls: List[int]) -> int:
    n, m = len(robots), len(walls)
    
    # 创建机器人数组，包括左右哨兵
    a = [(robots[i], distance[i]) for i in range(n)]
    # 添加左右哨兵
    a = [(-math.inf, 0)] + sorted(a, key=lambda x: x[0]) + [(math.inf, 0)]
    walls.sort()
    
    f0, f1 = 0, 0
    left, cur = 0, 0
    right0, right1 = 0, 0
    
    for i in range(1, n + 1):
        x, d = a[i]
        prev_x = a[i - 1][0]
        next_x = a[i + 1][0]
        
        # 往左射，墙的坐标范围为 [leftX, x]
        leftX = max(x - d, prev_x + 1)  # +1 表示不能射到左边那个机器人
        # 移动左指针
        while left < m and walls[left] < leftX:
            left += 1
        # 移动当前指针到当前位置
        while cur < m and walls[cur] < x:
            cur += 1
        cur1 = cur
        # 如果当前墙正好在机器人位置，跳过它
        if cur < m and walls[cur] == x:
            cur += 1
        # 往左射能摧毁的墙数量
        leftRes = f0 + cur - left
        
        # 往右射，下一个机器人往左射
        rightX = min(x + d, next_x - a[i + 1][1] - 1)
        while right0 < m and walls[right0] <= rightX:
            right0 += 1
        f0 = max(leftRes, f1 + right0 - cur1)
        
        # 往右射，下一个机器人往右射
        rightX = min(x + d, next_x - 1)
        while right1 < m and walls[right1] <= rightX:
            right1 += 1
        f1 = max(leftRes, f1 + right1 - cur1)
    
    return f1

# 测试代码
if __name__ == "__main__":
    robots = [10, 2]
    distance = [5, 1]
    walls = [5, 2, 7]
    result = maxWalls(robots, distance, walls)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdint>

using namespace std;

struct Pair {
    int x;
    int d;

    Pair(int x = 0, int d = 0) : x(x), d(d) {}
};

int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
    int n = robots.size();
    int m = walls.size();

    // 创建机器人数组，包括左右哨兵
    vector<Pair> a(n + 2);
    for (int i = 0; i < n; i++) {
        a[i] = Pair(robots[i], distance[i]);
    }
    a[n + 1] = Pair(INT_MAX, 0); // 右哨兵

    // 按坐标排序
    sort(a.begin(), a.end(), [](const Pair& p1, const Pair& p2) {
        return p1.x < p2.x;
    });
    sort(walls.begin(), walls.end());

    int64_t f0 = 0, f1 = 0; // 使用64位整数防止溢出
    int left = 0, cur = 0;
    int right0 = 0, right1 = 0;

    for (int i = 1; i <= n; i++) {
        Pair p = a[i];

        // 往左射，墙的坐标范围为 [leftX, p.x]
        int leftX = max(p.x - p.d, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
        while (left < m && walls[left] < leftX) {
            left++;
        }
        while (cur < m && walls[cur] < p.x) {
            cur++;
        }
        int cur1 = cur;
        if (cur < m && walls[cur] == p.x) {
            cur++;
        }
        int64_t leftRes = f0 + (cur - left); // 下标在 [left, cur-1] 中的墙都能摧毁

        // 往右射，右边那个机器人往左射，墙的坐标范围为 [p.x, rightX]
        Pair q = a[i + 1];
        int rightX = min(p.x + p.d, q.x - q.d - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
        while (right0 < m && walls[right0] <= rightX) {
            right0++;
        }
        f0 = max(leftRes, f1 + (right0 - cur1)); // 下标在 [cur1, right0-1] 中的墙都能摧毁

        // 往右射，右边那个机器人往右射，墙的坐标范围为 [p.x, rightX]
        rightX = min(p.x + p.d, q.x - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
        while (right1 < m && walls[right1] <= rightX) {
            right1++;
        }
        f1 = max(leftRes, f1 + (right1 - cur1)); // 下标在 [cur1, right1-1] 中的墙都能摧毁
    }

    return f1;
}

int main() {
    vector<int> robots = {10, 2};
    vector<int> distance = {5, 1};
    vector<int> walls = {5, 2, 7};

    int result = maxWalls(robots, distance, walls);
    cout << result << endl;

    return 0;
}