LeetCode 475：供暖器——排序 + 二分查找

题目

一条水平线上有若干房屋和供暖器。每个供暖器的覆盖范围是以自身位置为中心、半径为 r 的区间。求覆盖所有房屋所需的最小半径。

例如：

text 复制代码 <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="lucide lucide-circle-chevron-left md-editor-icon"><circle cx="12" cy="12" r="10"/><path d="m14 16-4-4 4-4"/></svg>

houses  = [1, 2, 3]
heaters = [2]
答案是 1

因为房屋 1 和 3 到供暖器 2 的距离都是 1。

核心思路

对于每一栋房屋，只需要找到距离它最近的供暖器。所有房屋中“最近供暖器距离”的最大值，就是答案。

供暖器排序后，对于房屋 house，可以用二分查找找到第一个大于等于它的位置：

这个位置的供暖器是右侧候选。
它前面的供暖器是左侧候选。
房屋到这两个候选的较小距离，就是房屋的最小供暖距离。

最后取所有房屋最小距离中的最大值。

二分查找实现

javascript 复制代码 <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="lucide lucide-circle-chevron-left md-editor-icon"><circle cx="12" cy="12" r="10"/><path d="m14 16-4-4 4-4"/></svg>

function lowerBound(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

lowerBound 返回第一个大于等于 target 的下标。如果返回值等于数组长度，说明右侧没有供暖器；如果返回值为 0，说明左侧没有供暖器。

完整代码

function findRadius(houses, heaters) {
  if (heaters.length === 0) {
    return 0;
  }

  const sortedHeaters = [...heaters].sort((a, b) => a - b);
  let answer = 0;

  for (const house of houses) {
    const rightIndex = lowerBound(sortedHeaters, house);
    let nearestDistance = Infinity;

    if (rightIndex < sortedHeaters.length) {
      nearestDistance = Math.min(
        nearestDistance,
        sortedHeaters[rightIndex] - house,
      );
    }

    if (rightIndex > 0) {
      nearestDistance = Math.min(
        nearestDistance,
        house - sortedHeaters[rightIndex - 1],
      );
    }

    answer = Math.max(answer, nearestDistance);
  }

  return answer;
}

console.log(findRadius([1, 2, 3], [2])); // 1
console.log(findRadius([1, 2, 3, 4], [1, 4])); // 1
console.log(findRadius([1, 5], [2])); // 3

复杂度分析

设房屋数量为 n，供暖器数量为 m：

排序供暖器：O(m log m)。
每栋房屋进行一次二分查找：O(n log m)。
总时间复杂度：O(m log m + n log m)。
额外空间复杂度：O(m)，因为代码复制了一份并排序供暖器；如果允许原地排序，则可以降为 O(1) 额外空间。

边界情况

房屋在所有供暖器左侧：只计算右侧候选。
房屋在所有供暖器右侧：只计算左侧候选。
房屋位置正好有供暖器：最近距离为 0。
供暖器位置重复：不会影响结果。
题目保证存在供暖器；代码中的空数组判断只是防御性处理。

为什么原来的多份代码需要整理

原文同时保留了 findRadius2、findRadius3 和 findRadius4 三个版本，并夹杂大量随机测试数据和调试输出。这样读者很难判断最终推荐哪一种实现，也无法看出不同实现的复杂度差异。

本文保留一个可以解释、验证和复用的二分查找方案，删除临时调试代码，并补充了边界条件和复杂度分析。