LeetCode 题解工作台
供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。 在加热器的加热半径范围内的每个房屋都可以获得供暖。 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。 注意 ：所有供暖器 heaters 都遵循你…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def findRadius(self, houses: List[int], heaters: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 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 * 1041 <= houses[i], heaters[i] <= 109
解题思路
方法一
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
def check(r):
m, n = len(houses), len(heaters)
i = j = 0
while i < m:
if j >= n:
return False
mi = heaters[j] - r
mx = heaters[j] + r
if houses[i] < mi:
return False
if houses[i] > mx:
j += 1
else:
i += 1
return True
left, right = 0, int(1e9)
while left < right:
mid = (left + right) >> 1
if check(mid):
right = mid
else:
left = mid + 1
return left
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Sorting both arrays is critical to avoid inefficient distance checks.
- question_mark
Binary search over the radius shows understanding of monotonic answer patterns.
- question_mark
Two-pointer or direct nearest heater evaluation ensures each candidate radius can be validated efficiently.
常见陷阱
外企场景- error
Assuming the nearest heater is always to the left or right without checking both sides.
- error
Using linear search for each house-heater pair, causing timeouts on large inputs.
- error
Forgetting to sort the heaters or houses, which breaks the binary search assumptions.
进阶变体
外企场景- arrow_right_alt
Determine the minimum number of heaters needed if all have a fixed radius.
- arrow_right_alt
Compute the maximum house distance from its nearest heater instead of minimal radius.
- arrow_right_alt
Place heaters optimally along the street to minimize total radius sum.