LeetCode 475. 供暖器
目录
题目描述
✅ 475. 供暖器
题意分析
一条直线上给定若干房屋坐标和若干供暖器坐标，所有供暖器共用同一个加热半径。要求这个半径最小取多少，才能让每一栋房屋都被至少一台供暖器覆盖。
「共用同一个半径」和「必须全部覆盖」这两条合起来，把问题从「怎么分配」变成了「取最大值」：只要半径不小于某栋房屋到它最近供暖器的距离，这栋房屋就被覆盖；要让所有房屋都满足，半径必须不小于这些距离中的最大者，而取到这个最大者就已经够用。所以答案是一个确定的量，不需要搜索。
两个数组都没有说明是有序的，也没有说明元素互不相同，甚至房屋和供暖器可能落在同一坐标上（此时距离为 0）。这些都是必须先处理干净的前提。
数组长度都在三万量级、坐标可达十亿量级。长度提示可以承受排序加对数级查找；坐标量级提示中间的差值不会溢出 32 位，但如果写出「左右坐标相加取中点」这类式子就有溢出风险。
边界情况：某栋房屋位于所有供暖器的左侧或右侧，此时它只有单侧的邻居可选；供暖器只有一台；房屋坐标与供暖器坐标完全重合。
解法：排序 + 二分
核心思路
按定义直接写就是双重循环：对每栋房屋扫一遍所有供暖器求最近距离，再对所有房屋取最大。结果正确，但当两个数组都是三万量级时，总比较次数接近九亿，明显超时。
瓶颈在于「每栋房屋都要看全部供暖器」。观察到求的是最近距离，而距离在数轴上是单峰的：把供暖器按坐标排好序后，随着下标从左往右推进，供暖器到某栋固定房屋的距离先单调下降、再单调上升。既然如此，最近的那台不可能出现在中间的任意位置，它一定是「第一台坐标不小于房屋坐标的供暖器」或者「它的前一台」，二者取近。
这就把每栋房屋的查询压缩成一次二分：在有序的供暖器数组里找下界（第一个不小于目标的位置），记作 $idx$。$idx$ 把数组切成两半，左半全部严格小于房屋坐标，右半全部不小于房屋坐标，因此候选只有 $heaters[idx-1]$ 和 $heaters[idx]$ 这两个。
于是整个算法维持的不变量是：遍历到第 $k$ 栋房屋时，答案变量保存的是前 $k$ 栋房屋各自最近距离的最大值。遍历结束时它就是全局答案。注意房屋数组不需要排序，因为每栋房屋的查询彼此独立，顺序无关。
解题步骤
- 先对供暖器数组排序。二分的全部前提就是有序，题目并未保证输入有序，这一步不能省。房屋数组无需排序，排了也不会更快。
- 把答案初始化为 0。0 是合法的下界，对应「每栋房屋都正好有一台供暖器与之重合」的情形，所以不需要用负无穷做哨兵。
- 对每栋房屋做一次下界二分，得到第一个坐标不小于房屋坐标的下标 $idx$。用「小于则左界右移、否则右界收到中点」的写法，区间取左闭右开，循环结束时左右重合于答案位置。
- 二分的右界初值取数组长度而不是长度减一。因为「所有供暖器都在房屋左侧」时正确答案就是长度本身，右界取到末位下标会让这个结果无法被表达。
- 按 $idx$ 分三种情况取距离：等于 0 说明房屋在所有供暖器左侧，只能用第一台；等于数组长度说明房屋在所有供暖器右侧，只能用最后一台；否则左右各算一次取较小者。两个边界分支必须显式写出，否则会读到越界下标。
- 用这个距离去更新答案的最大值。这里是取最大而不是取最小——每栋房屋内部取最近（最小），房屋之间取最难覆盖的那栋（最大），两个方向不能搞反。
以
houses = [1, 2, 3, 4]、heaters = [1, 4]走一遍：排序后供暖器仍是[1, 4]，答案初始为 0。房屋 1：二分找第一个不小于 1 的位置。左界 0、右界 2，中点 1 处的值 4 不小于 1，右界收到 1；再取中点 0，值 1 不小于 1，右界收到 0，左右重合，$idx = 0$。命中左边界分支，距离为 $1 - 1 = 0$。答案仍为 0。
房屋 2：二分中点 1 处的值 4 不小于 2，右界收到 1；中点 0 处的值 1 小于 2，左界推到 1，与右界重合，$idx = 1$。落在中间分支，左侧距离 $2 - 1 = 1$，右侧距离 $4 - 2 = 2$，取较小的 1。答案从 0 更新为 1。
房屋 3：同样得到 $idx = 1$。左侧距离 $3 - 1 = 2$，右侧距离 $4 - 3 = 1$，取 1。答案维持 1。
房屋 4：中点 1 处的值 4 不小于 4，右界收到 1；中点 0 处的值 1 小于 4，左界推到 1，$idx = 1$。左侧距离 $4 - 1 = 3$，右侧距离 $4 - 4 = 0$，取 0。答案维持 1。
遍历结束返回 1。验证一下：半径取 1 时，位置 1 的供暖器覆盖区间 $[0, 2]$，位置 4 的覆盖 $[3, 5]$，四栋房屋恰好全被覆盖；半径取 0 时房屋 2 和 3 都无人覆盖，所以 1 确实是最小值。
再看一个单侧边界的例子
houses = [1, 5]、heaters = [10]：房屋 1 二分得 $idx = 0$，走左边界分支，距离 $10 - 1 = 9$；房屋 5 同样得 $idx = 0$，距离 $10 - 5 = 5$。答案取两者最大值 9。若漏掉这个分支去读 $heaters[-1]$，程序会直接崩溃。
代码实现
class Solution {
// 将供暖器位置排序后，对任意房屋，最近供暖器只可能在插入位置的左侧或右侧。
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int answer = 0;
for (int house : houses) {
int idx = lowerBound(heaters, house);
int distance;
if (idx == 0) {
distance = heaters[0] - house;
} else if (idx == heaters.length) {
distance = house - heaters[heaters.length - 1];
} else {
int leftDistance = house - heaters[idx - 1];
int rightDistance = heaters[idx] - house;
distance = Math.min(leftDistance, rightDistance);
}
answer = Math.max(answer, distance);
}
return answer;
}
private int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
func findRadius(houses []int, heaters []int) int {
// 将供暖器位置排序后，对任意房屋，最近供暖器只可能在插入位置的左侧或右侧。
sort.Ints(heaters)
answer := 0
for _, house := range houses {
idx := lowerBound475(heaters, house)
distance := 0
if idx == 0 {
distance = heaters[0] - house
} else if idx == len(heaters) {
distance = house - heaters[len(heaters)-1]
} else {
leftDistance := house - heaters[idx-1]
rightDistance := heaters[idx] - house
if leftDistance < rightDistance {
distance = leftDistance
} else {
distance = rightDistance
}
}
if distance > answer {
answer = distance
}
}
return answer
}
func lowerBound475(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(n \log n + m \log n)$，其中 $n$ 是供暖器数量、$m$ 是房屋数量。排序占 $O(n \log n)$，之后每栋房屋做一次二分，各占 $O(\log n)$，两部分相加即为总量。
- 空间复杂度：$O(1)$（不计排序自身的开销），主体逻辑只用了下标、距离和答案几个标量，没有开辟与输入规模相关的辅助数组。
关键点总结
- 「统一参数 + 全部满足」的最优化问题，答案往往就是各个单体需求的最大值，识别出这一点就不必再上二分答案那套框架。
- 数轴上求最近点的通用手法是：把候选排序，二分定位插入点，只检查左右两个邻居。这条模板适用于所有一维最近邻查询。
- 下界二分的右界必须初始化为数组长度而非末位下标，否则「全部元素都小于目标」这一情形无法表达。
- 内层取最小、外层取最大，两个方向不能混。写代码前先用一句话说清「每栋房屋要什么、房屋之间要什么」，能避免绝大多数方向性错误。
- 输入未声明有序时一定要自己排序。题目描述里没有「已排序」三个字，就默认它是乱的。
- 面试视角：先给出双重循环基线并算出它的量级，再说明「排序后最近邻只在插入点两侧」的观察。若面试官追问还能不能更快，可以答：把房屋也排序后用双指针同向扫描，能把两次二分省成一次线性归并，总复杂度变成两次排序加一次线性扫描。
易错点总结
- 错误写法：忘记对供暖器排序就直接二分。
heaters = [4, 1]、houses = [2]→ 二分在无序数组上返回的位置没有意义，可能得出距离 2 而不是正确的 1。- 错误写法：$idx$ 等于 0 时不做特判，直接读
heaters[idx - 1]。houses = [1, 5]、heaters = [10]→ 读到下标 -1，抛出数组越界异常。- 错误写法：$idx$ 等于数组长度时不做特判，直接读
heaters[idx]。houses = [10]、heaters = [1]→ 同样越界崩溃。
错误写法：下界二分的右界初始化为 heaters.length - 1。houses = [10]、heaters = [1, 2]→ 循环无法返回 2 这个位置，$idx$ 停在 1，算出的距离是 $2 - 10 = 8$ 时看似正确，但在需要区分「插入到末尾」的分支判断上会走错分支。 - 错误写法：房屋之间取最小值而不是最大值。
houses = [1, 2, 3, 4]、heaters = [1, 4]→ 返回 0（来自房屋 1），正确答案是 1，因为半径 0 覆盖不了房屋 2。- 错误写法：中间分支只取右侧距离，或只取左侧距离。
houses = [3]、heaters = [1, 4]→ 只取左侧会得到 2，正确答案是 1。- 错误写法：把答案初始化为某个正数（例如第一栋房屋到第一台供暖器的距离）而没有真正参与后续比较。所有房屋都与供暖器重合的用例 → 返回一个非零值，正确答案是 0。
- 错误写法：二分中点写成
(left + right) / 2并且左右界存的是坐标而非下标。坐标接近十亿的用例 → 相加溢出 32 位变成负数，中点落到数组外。- 错误写法：认为房屋数组也必须排序，于是原地排序了输入的
houses。虽然不影响本题答案，但改动了调用方的数组，在要求不修改入参的场景下是副作用；真正需要排序的只有供暖器。- 错误写法：用「供暖器和房屋逐个配对」的贪心，即第 $i$ 栋房屋归第 $i$ 台供暖器。
houses = [1, 2, 3]、heaters = [2]→ 数量不等时配对根本无法进行，且即使数量相等，最近供暖器也未必与序号对应。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 下界二分的裸题，正是本题内层函数的语义 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 同一模板求上下界，考察边界收缩方向的对称性 |
| 658. 找到 K 个最接近的元素 | 中等 | 定位插入点后向两侧扩展，比较规则含字典序平局 |
| 1011. 在 D 天内送达包裹的能力 | 中等 | 答案本身不可直接算出，须对答案二分并写可行性判定 |
| 410. 分割数组的最大值 | 困难 | 同为最小化最大值，但判定函数需要贪心分段 |
| 719. 找出第 K 小的数对距离 | 困难 | 对距离二分，配合双指针统计不超过某距离的数对个数 |
| 278. 第一个错误的版本 | 简单 | 布尔序列上找分界点，检验边界写法是否会死循环 |