475. 供暖器
题目描述
房屋和供暖器都位于同一条数轴上，houses 给出各房屋的位置，heaters 给出各供暖器的位置。
所有供暖器共用同一个加热半径 r：位于 x 的供暖器能让 [x - r, x + r] 内的房屋取暖。
返回能让每间房屋至少被一个供暖器覆盖的最小 r。
示例 1
输入：houses = [1,2,3], heaters = [2] 输出：1
解释：唯一的供暖器在 2，半径 1 可覆盖 1 到 3。
示例 2
输入：houses = [1,2,3,4], heaters = [1,4] 输出：1
解释：供暖器在 1 和 4，半径 1 时 2 由前者覆盖、3 由后者覆盖。
示例 3
输入：houses = [1,5], heaters = [2] 输出：3
解释：房屋 5 距离唯一的供暖器 2 有 3 远，半径至少为 3。
数据范围
1 <= houses.length, heaters.length <= 3 * 10^41 <= houses[i], heaters[i] <= 10^9
解题思路：排序 + 二分查找
每间房屋只需要离它最近的供暖器。把 heaters 排序，对房屋 h 用 bisect_left 找第一个 >= h 的供暖器 heaters[j]，最近的只可能是它或它左边的 heaters[j-1]。取两者距离较小值，就是这间房屋需要的半径；答案是所有房屋需要半径的最大值。
为什么正确
ans 是已处理房屋各自到最近供暖器距离的最大值。
复杂度分析
排序 O(m log m)，每间房屋二分 O(log m)，总时间 O((n + m) log m)，额外空间 O(1)（不计排序）。
易错点
j 可能等于 0 或 len(heaters)，这时只有一侧有供暖器，要先判断边界再取值。houses 不需要排序，但 heaters 必须排序。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
heaters.sort()
ans = 0
for h in houses:
j = bisect_left(heaters, h)
d = float('inf')
if j < len(heaters):
d = heaters[j] - h
if j > 0:
d = min(d, h - heaters[j - 1])
ans = max(ans, d)
return ansclass Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int ans = 0;
for (int h : houses) {
int lo = 0, hi = heaters.length; while (lo < hi) { int m = (lo + hi) >>> 1; if (heaters[m] < h) lo = m + 1; else hi = m; } int j = lo;
int d = Integer.MAX_VALUE;
if (j < heaters.length) {
d = heaters[j] - h;
}
if (j > 0) {
d = Math.min(d, h - heaters[j - 1]);
}
ans = Math.max(ans, d);
}
return ans;
}
}class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int ans = 0;
for (int h : houses) {
int j = lower_bound(heaters.begin(), heaters.end(), h) - heaters.begin();
int d = INT_MAX;
if (j < (int)heaters.size()) {
d = heaters[j] - h;
}
if (j > 0) {
d = min(d, h - heaters[j - 1]);
}
ans = max(ans, d);
}
return ans;
}
};func findRadius(houses []int, heaters []int) int {
sort.Ints(heaters)
ans := 0
for _, h := range houses {
j := sort.SearchInts(heaters, h)
d := math.MaxInt64
if j < len(heaters) {
d = heaters[j] - h
}
if j > 0 {
d = min(d, h-heaters[j-1])
}
ans = max(ans, d)
}
return ans
}var findRadius = function(houses, heaters) {
heaters.sort((a, b) => a - b);
let ans = 0;
for (const h of houses) {
let lo = 0, hi = heaters.length; while (lo < hi) { const m = (lo + hi) >> 1; if (heaters[m] < h) lo = m + 1; else hi = m; } const j = lo;
let d = Infinity;
if (j < heaters.length) {
d = heaters[j] - h;
}
if (j > 0) {
d = Math.min(d, h - heaters[j - 1]);
}
ans = Math.max(ans, d);
}
return ans;
};function findRadius(houses: number[], heaters: number[]): number {
heaters.sort((a, b) => a - b);
let ans = 0;
for (const h of houses) {
let lo = 0, hi = heaters.length; while (lo < hi) { const m = (lo + hi) >> 1; if (heaters[m] < h) lo = m + 1; else hi = m; } const j = lo;
let d = Infinity;
if (j < heaters.length) {
d = heaters[j] - h;
}
if (j > 0) {
d = Math.min(d, h - heaters[j - 1]);
}
ans = Math.max(ans, d);
}
return ans;
}其他解法
二分只需对供暖器排序，每个房屋独立查找；双指针利用两个有序数组的单调性，用一次合并式扫描代替多次二分。
解法 2：排序 + 双指针 时间 O(n log n + m log m)，空间 O(log n + log m)
把房屋和供暖器都排序。按顺序处理房屋时，离它最近的供暖器下标只会向右移动：只要下一个供暖器距离不比当前的远，就把指针右移。每个房屋取到最近供暖器的距离，所有房屋取最大值即为答案。
扫描部分是线性的，不需要二分。但房屋数组也要排序，并且要想清楚指针单调移动的条件（相等时也要右移）。
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses = sorted(houses)
heaters = sorted(heaters)
ans = j = 0
for h in houses:
# 房屋有序，最近的供暖器下标只会右移
while j + 1 < len(heaters) and abs(heaters[j + 1] - h) <= abs(heaters[j] - h):
j += 1
ans = max(ans, abs(heaters[j] - h))
return ansclass Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int ans = 0, j = 0, m = heaters.length;
for (int h : houses) {
while (j + 1 < m && Math.abs(heaters[j + 1] - h) <= Math.abs(heaters[j] - h)) j++;
ans = Math.max(ans, Math.abs(heaters[j] - h));
}
return ans;
}
}class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int ans = 0, j = 0, m = heaters.size();
for (int h : houses) {
while (j + 1 < m && abs(heaters[j + 1] - h) <= abs(heaters[j] - h)) j++;
ans = max(ans, abs(heaters[j] - h));
}
return ans;
}
};func findRadius(houses []int, heaters []int) int {
sort.Ints(houses)
sort.Ints(heaters)
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
ans, j := 0, 0
for _, h := range houses {
for j+1 < len(heaters) && abs(heaters[j+1]-h) <= abs(heaters[j]-h) {
j++
}
if d := abs(heaters[j] - h); d > ans {
ans = d
}
}
return ans
}var findRadius = function(houses, heaters) {
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
let ans = 0, j = 0;
for (const h of houses) {
while (j + 1 < heaters.length && Math.abs(heaters[j + 1] - h) <= Math.abs(heaters[j] - h)) j++;
ans = Math.max(ans, Math.abs(heaters[j] - h));
}
return ans;
};function findRadius(houses: number[], heaters: number[]): number {
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
let ans = 0, j = 0;
for (const h of houses) {
while (j + 1 < heaters.length && Math.abs(heaters[j + 1] - h) <= Math.abs(heaters[j] - h)) j++;
ans = Math.max(ans, Math.abs(heaters[j] - h));
}
return ans;
}