475.供暖器(Medium)

题目描述

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，在加热器的加热半径范围内的每个房屋都可以获得供暖。请你找出并返回可以覆盖所有房屋的最小加热半径。

样例

Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

题解

需要两次遍历，第一次遍历 house ，再从 heaters 第二次遍历中找到离 house 最近的加热器，得到半径。

所有 house 的半径的最大值一定是我们的最小加热半径。

这里从 heaters 找到加热器的过程可以通过折半查找优化。

Python 代码示例

# 两次遍历，Python 超时
class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        radis = -1
        for house in houses:
            house_distance = min(abs(heater - house) for heater in heaters)
            radis = max(radis, house_distance)
        return radis
 
# 折半查找
import math 
class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        def findNearnest(house):
            left, right = 0, len(heaters) - 1
            while left < right:
                mid = (left + right ) >> 1
                if heaters[mid] < house:
                    left = mid + 1
                else:
                    right = mid 
            # left 为第一个大于house的值，离 house 最近的一定是 left 和 left - 1
            dist1 = abs(heaters[left] - house) if left < len(heaters) else math.inf  # 处理边界值
            dist2 = abs(heaters[left - 1] - house)  if left > 0 else math.inf 
            return min(dist1, dist2)
        
        heaters.sort()
        radis = -1
        for house in houses:
            house_distance = findNearnest(house)
            if house_distance > radis:
                radis = house_distance
        return radis