如何以低于O(n)复杂度确定点所在的最优矩形（含重叠处理）

给定一组矩形，每个矩形由左上角坐标(x0, y0)和右下角坐标(x1, y1)定义。需要找出**完全包含目标点(X,Y)**的最优矩形：

• 若存在多个重叠的包含矩形，优先选择面积最小的；
• 后续可优化为选择距矩形顶点最近的。

输入示例 #

目标点：(1450, 380)
矩形列表：

[
  {
    "x0": 1797,
    "x1": 1854,
    "y0": 333,
    "y1": 434
  },
  {
    "x0": 1671,
    "x1": 1688,
    "y0": 423,
    "y1": 434
  },
  {
    "x0": 1565,
    "x1": 1594,
    "y0": 366,
    "y1": 378
  },
  {
    "x0": 1547,
    "x1": 1552,
    "y0": 112,
    "y1": 146
  },
  {
    "x0": 1439,
    "x1": 1457,
    "y0": 373,
    "y1": 396
  }
]

输出示例 #

{
  "x0": 1439,
  "x1": 1457,
  "y0": 373,
  "y1": 396
}

当前已有遍历所有矩形的O(n)复杂度解法，问是否存在复杂度低于O(n)的更优方案？

是否存在更优方案，取决于查询场景是单次查询还是多次查询：

1. 单次查询场景 #

不存在比O(n)更优的方案。因为要确认每个矩形是否包含目标点，没有预处理的情况下，无法跳过任何一个矩形——一旦跳过，就有可能漏掉符合条件的最优矩形，必须逐个检查。

2. 多次查询场景（可预处理） #

通过预处理可以将查询复杂度降到O(log n + k)（k为符合条件的矩形数量，通常远小于n），以下是两种可行方案：

方案一：空间划分结构（四叉树/范围树） #

• 预处理阶段：将所有矩形按照空间区域划分到四叉树或范围树中，把空间拆分为层级化的子区域，每个子区域存储覆盖它的矩形。
• 查询阶段：直接定位到目标点所在的子区域，只检查该区域内的矩形，无需遍历全部矩形。这种结构适合矩形分布有规律、查询次数多的场景。

方案二：排序+二分查找筛选 #

• 预处理阶段：
  1. 对所有矩形按x0降序、x1升序排序，通过二分快速筛选出满足x0 ≤ X ≤ x1的矩形；
  2. 对筛选后的矩形按y0降序、y1升序排序，进一步筛选出满足y0 ≤ Y ≤ y1的矩形。
• 查询阶段：通过两次二分查找快速缩小候选范围，再从候选矩形中选出面积最小的（或后续优化的距顶点最近的）。预处理时间复杂度为O(n log n)，单次查询效率远高于O(n)。

内容的提问来源于stack exchange，提问作者Vaibhav More