离散化处理

离散化是将原始数据映射到更小的范围内，同时保持相对顺序不变。对于墙壁位置数据，需要将所有可能的位置进行排序并去重，建立映射关系。例如，给定墙壁位置数组 [1, 5, 3, 7]，排序去重后得到 [1, 3, 5, 7]，映射为 {1:0, 3:1, 5:2, 7:3}。

线段树构建

线段树用于高效查询区间信息和更新操作。每个节点存储区间的最大值或其他统计信息。构建线段树时，叶子节点对应离散化后的墙壁位置。初始化时，每个叶子节点的值为对应位置的墙壁强度。非叶子节点的值为子节点值的最大值。

二分查找策略

通过二分查找确定机器人能够摧毁的最大墙壁数目。设定左右边界，左边界为 0，右边界为墙壁总数。每次取中间值 mid，检查是否存在连续 mid 个墙壁可以被机器人摧毁。检查过程利用线段树快速查询区间最大值。

区间查询优化

在二分查找的验证阶段，使用线段树查询所有长度为 mid 的连续区间的最小最大值。若存在某个区间的最大值小于等于机器人的力量值，则说明可以摧毁 mid 个连续墙壁。调整二分查找的边界，直到找到最大可行的 mid。

复杂度分析

离散化的时间复杂度为 $O(n \log n)$，线段树构建为 $O(n)$。二分查找的验证阶段每次查询线段树的时间为 $O(\log n)$，总复杂度为 $O(n \log n)$。整体算法的时间复杂度为 $O(n \log n)$。

代码示例

def maxDestroyedWalls(walls, power):
    sorted_unique = sorted(set(walls))
    mapping = {v: i for i, v in enumerate(sorted_unique)}
    n = len(sorted_unique)
    
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [0] * (2 * self.size)
            for i in range(self.n):
                self.tree[self.size + i] = data[i]
            for i in range(self.size - 1, 0, -1):
                self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])
        
        def query_max(self, l, r):
            res = 0
            l += self.size
            r += self.size
            while l <= r:
                if l % 2 == 1:
                    res = max(res, self.tree[l])
                    l += 1
                if r % 2 == 0:
                    res = max(res, self.tree[r])
                    r -= 1
                l //= 2
                r //= 2
            return res
    
    data = [0] * n
    for wall in walls:
        data[mapping[wall]] = wall
    st = SegmentTree(data)
    
    left, right = 0, len(walls)
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        possible = False
        for i in range(n - mid + 1):
            max_val = st.query_max(i, i + mid - 1)
            if max_val <= power:
                possible = True
                break
        if possible:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer