问题分析

我们需要在三维空间中找到与坐标轴平行的长方体围栏，使得包含的行星数量在 $[k, \lceil \frac{3}{2}k \rceil]$ 范围内。这是一个三维空间的范围构造问题。

核心思想

降维递归搜索：将三维问题分解为在三个维度上依次确定边界，通过递归搜索找到满足条件的解。

关键算法

1. 递归维度处理

• 从第 0 维（x 轴）开始处理，依次处理 y 轴、z 轴
• 在每个维度上，按坐标值将点分组
• 对每个分组递归处理下一个维度

2. 滑动窗口搜索

在当前维度上维护滑动窗口 $[j, i]$：

• 累加窗口内点数 sum
• 当 sum > R 时移动左指针 j 缩小窗口
• 当 sum ∈ [L, R] 时找到可行解

3. 边界确定策略

对于找到的窗口 $[j, i]$：

• 当前维度边界直接取窗口边界
• 其他维度边界取所有点的最小和最大坐标值
• 保证围栏包含所有选中的点

4. 相邻合并备选

如果单一坐标值分组无法找到解：

• 递归处理每个分组的子问题
• 合并相邻坐标值的分组继续搜索

复杂度分析

• 时间复杂度：最坏 $O(n^2)$，但实际运行效率较高
• 空间复杂度：$O(n)$ 用于存储和递归

算法优势

1. 完备性：通过递归和合并策略，能够搜索到各种可能的解
2. 实用性：对于实际数据能够快速找到解
3. 灵活性：支持输出任意可行解