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

解题思路

核心思想是记忆化搜索 (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)。

Python3 代码

```python
from bisect import bisect_left
from functools import cache
from typing import List

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n = len(robots)
        
        # 将机器人按位置排序，并配对距离
        arr = sorted(zip(robots, distance), key=lambda x: x[0])
        
        # 墙壁排序，便于二分查找
        walls.sort()
        
        @cache
        def dfs(i: int, j: int) -> int:
            """
            i: 当前考虑的机器人索引（从右往左处理）
            j: 右边相邻机器人的射击方向（0=左，1=右）
            返回：从机器人0到i能摧毁的最大墙壁数
            """
            if i < 0:
                return 0
            
            pos, dist = arr[i]
            
            # ========== 选项1：当前机器人向左射击 ==========
            left = pos - dist
            if i > 0:
                # 被左边相邻机器人阻挡，子弹最多到左边机器人位置+1
                left = max(left, arr[i - 1][0] + 1)
            
            # 二分查找 walls 中 [left, pos] 范围内的墙壁数量
            l = bisect_left(walls, left)
            r = bisect_left(walls, pos + 1)
            ans = dfs(i - 1, 0) + (r - l)
            
            # ========== 选项2：当前机器人向右射击 ==========
            right = pos + dist
            if i + 1 < n:
                if j == 0:
                    # 右边机器人向左射，阻挡位置为右边机器人的左边界-1
                    right = min(right, arr[i + 1][0] - arr[i + 1][1] - 1)
                else:
                    # 右边机器人向右射，阻挡位置为右边机器人位置-1
                    right = min(right, arr[i + 1][0] - 1)
            
            # 二分查找 walls 中 [pos, right] 范围内的墙壁数量
            l = bisect_left(walls, pos)
            r = bisect_left(walls, right + 1)
            ans = max(ans, dfs(i - 1, 1) + (r - l))
            
            return ans
        
        # 从最后一个机器人开始，假设右边没有机器人，用 j=1 作为边界
        result = dfs(n - 1, 1)
        dfs.cache_clear()  # 清理缓存，避免内存泄漏
        return result
```

关键点说明

要点    说明    
排序    机器人和墙壁都按位置排序，便于二分查找和相邻关系处理    
向左射击的左边界    `max(pos - dist, left_robot_pos + 1)`，确保不会穿过左边机器人    
向右射击的右边界    取决于右边机器人的射击方向，若右边向左射则受其左边界限制，否则受其位置限制    
二分查找    `bisect_left` 用于快速统计 walls 数组中某区间内的墙壁数量    
记忆化    `@cache` 装饰器自动缓存 `dfs(i, j)` 的结果，避免重复计算    
缓存清理    `dfs.cache_clear()` 防止在 LeetCode 多次调用时内存泄漏    

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