友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
475. 供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: houses = [1,2,3], heaters = [2] 输出: 1 解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。
示例 2:
输入: houses = [1,2,3,4], heaters = [1,4] 输出: 1 解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。
示例 3：
输入：houses = [1,5], heaters = [2] 输出：3
提示：
-
1 <= houses.length, heaters.length <= 3 * 104 -
1 <= houses[i], heaters[i] <= 109
思路分析
对加热器进行排序，利用二分查找对每个房子在加热器中寻找距离房子最近的左侧节点；下一个节点即距离房子最近的右侧节点。计算距离房子最近的距离，距离最近的就是最佳加热器。对于所有房子来说，这些距离中的最大距离即可满足加热所有房子的要求。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-09-01 22:08:15
*/
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int result = 0;
for (int house : houses) {
// 寻找 house 左侧最近加热器
int left = binarySearch(heaters, house);
int right = left + 1;
int leftDistance = left < 0 ? Integer.MAX_VALUE : house - heaters[left];
int rightDistance = right >= heaters.length ? Integer.MAX_VALUE : heaters[right] - house;
// 选择距离房子 house 最近的加热器
int distance = Math.min(leftDistance, rightDistance);
result = Math.max(result, distance);
}
return result;
}
private int binarySearch(int[] nums, int target) {
if (target < nums[0]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left - 1;
}