这是 LeetCode 3661 "Maximum Walls Destroyed by Robots" 的 Rust 实现。

解题思路

核心思想是记忆化搜索 (Memoized DFS)：

1. 预处理：将机器人按位置排序，墙壁也排序。
2. 状态设计：`dfs(i, j)` 表示考虑前 `i` 个机器人（从右往左处理），第 `i+1` 个机器人（右侧相邻）的射击方向为 `j`（0=左，1=右）时，能摧毁的最大墙壁数。
3. 转移：
   - 向左射击：子弹范围 `[robot[i] - distance[i], robot[i]]`，但会被左边相邻机器人阻挡，所以左边界至少为 `robot[i-1] + 1`。
   - 向右射击：子弹范围 `[robot[i], robot[i] + distance[i]]`，但会被右边相邻机器人阻挡。阻挡位置取决于右边机器人是向左还是向右射击：
     - 若右边机器人向左射，阻挡位置为 `robot[i+1] - distance[i+1] - 1`
     - 若右边机器人向右射，阻挡位置为 `robot[i+1] - 1`
4. 统计墙壁：用二分查找在排序后的 walls 数组中统计范围内的墙壁数量。

时间复杂度：O(n \log n + m \log m)，空间复杂度：O(n)。

Rust 代码

```rust
use std::cmp::{max, min};

impl Solution {
    pub fn max_walls(robots: Vec<i32>, distance: Vec<i32>, walls: Vec<i32>) -> i32 {
        let n = robots.len();
        let mut arr: Vec<(i32, i32)> = robots.into_iter()
            .zip(distance.into_iter())
            .collect();
        // 按机器人位置排序
        arr.sort_by_key(|&(pos, _)| pos);
        
        let mut walls = walls;
        walls.sort();
        
        // 记忆化数组，f[i][j] 表示处理到第 i 个机器人，右边机器人方向为 j 时的最大摧毁数
        // j: 0 = 左边机器人向左射, 1 = 左边机器人向右射
        let mut memo: Vec<Vec<Option<i32>>> = vec![vec![None; 2]; n];
        
        fn dfs(
            i: isize,
            j: usize,
            arr: &[(i32, i32)],
            walls: &[i32],
            memo: &mut Vec<Vec<Option<i32>>>,
            n: usize,
        ) -> i32 {
            if i < 0 {
                return 0;
            }
            let ui = i as usize;
            if let Some(val) = memo[ui][j] {
                return val;
            }
            
            let (pos, dist) = arr[ui];
            
            // 向左射击
            let mut left = pos - dist;
            if ui > 0 {
                // 被左边相邻机器人阻挡，子弹最多到左边机器人位置+1（不包含机器人本身）
                left = max(left, arr[ui - 1].0 + 1);
            }
            let l = lower_bound(walls, left);
            let r = lower_bound(walls, pos + 1);
            let mut ans = dfs(i - 1, 0, arr, walls, memo, n) + (r - l) as i32;
            
            // 向右射击
            let mut right = pos + dist;
            if ui + 1 < n {
                if j == 0 {
                    // 右边机器人向左射，阻挡位置为右边机器人的左边界-1
                    right = min(right, arr[ui + 1].0 - arr[ui + 1].1 - 1);
                } else {
                    // 右边机器人向右射，阻挡位置为右边机器人位置-1
                    right = min(right, arr[ui + 1].0 - 1);
                }
            }
            let l = lower_bound(walls, pos);
            let r = lower_bound(walls, right + 1);
            ans = max(ans, dfs(i - 1, 1, arr, walls, memo, n) + (r - l) as i32);
            
            memo[ui][j] = Some(ans);
            ans
        }
        
        // 从最后一个机器人开始，假设右边没有机器人，用 j=1 作为边界
        dfs(n as isize - 1, 1, &arr, &walls, &mut memo, n)
    }
}

// 二分查找 lower_bound：第一个 >= target 的位置
fn lower_bound(arr: &[i32], target: i32) -> usize {
    let mut lo = 0;
    let mut hi = arr.len();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if arr[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}
```

关键点说明

要点    说明    
排序    机器人和墙壁都按位置排序，便于二分查找和相邻关系处理    
向左射击的左边界    `max(pos - dist, left_robot_pos + 1)`，确保不会穿过左边机器人    
向右射击的右边界    取决于右边机器人的射击方向，若右边向左射则受其左边界限制，否则受其位置限制    
二分查找    `lower_bound` 用于快速统计 walls 数组中某区间内的墙壁数量    
记忆化    `memo[i][j]` 避免重复计算，j 表示右侧机器人的射击方向    

该解法与官方题解一致，时间复杂度 O((n+m)\log(n+m))，空间复杂度 O(n)。