1.题目基本信息

1.1.题目描述

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

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

注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

1.2.题目地址

https://leetcode.cn/problems/heaters/description/

2.解题方法

2.1.解题思路

问题本质：找每个房子距离最近供暖器的距离的最大值

思路1：二分查找+排序。

思路2：双指针+排序。

2.2.解题步骤

思路1：二分查找+排序

• 第一步，将houses和heaters升序排列

• 第二步，二分查找每个房子距离最近供暖器的距离，然后取这些距离的最大值即为题解

  • 2.1.二分查找heaters中第一个大于等于houses[i]的位置，这里采用左右闭区间的模式，最终的left即为需要求的位置

  • 2.2.根据heaters中第一个大于houses[i]的元素，找到距离houses[i]最近的供暖器的位置，并更新维护变量

思路2：双指针+排序

• 第一步，将houses和heaters进行升序排列，并在heaters的后面分别加上哨兵

• 第二步，构建维护变量。指针i指向houses当前进行比较的房子；指针j指向heaters中供暖器的位置，j指针一直向着距离当前house更近的方向移动

3.解题代码

python3代码-二分查找+排序

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        # 思路1：二分查找+排序。本质问题：找每个房子距离最近供暖器的距离的最大值
        # 第一步，将houses和heaters升序排列
        m, n = len(houses), len(heaters)
        houses.sort()
        heaters.sort()
        # 第二步，二分查找每个房子距离最近供暖器的距离，然后取这些距离的最大值即为题解
        result = 0
        for i in range(m):
            # 2.1.二分查找heaters中第一个大于等于houses[i]的位置，这里采用左右闭区间的模式，最终的left即为需要求的位置
            left, right = 0, n - 1
            while left <= right:
                mid = left + (right - left) // 2
                if heaters[mid] >= houses[i]:
                    right = mid - 1
                else:
                    left = mid + 1
            # 2.2.根据heaters中第一个大于houses[i]的元素，找到距离houses[i]最近的供暖器的位置，并更新维护变量
            index = left
            if 0 < index < n:
                result = max(result, min(heaters[index] - houses[i], houses[i] - heaters[index - 1]))
            elif index == 0:
                result = max(result, heaters[index] - houses[i])
            else:
                result = max(result, houses[i] - heaters[index - 1])
        return result

python3代码-双指针+排序

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        # 思路2：双指针+排序。本质问题：找每个房子到最近供暖器的距离的最大值
        m, n = len(houses), len(heaters)
        # 第一步，将houses和heaters进行升序排列，并在heaters的后面分别加上哨兵
        houses.sort()
        heaters.sort()
        heaters.append(inf)
        # 第二步，构建维护变量。指针i指向houses当前进行比较的房子；指针j指向heaters中供暖器的位置，j指针一直向着距离当前house更近的方向移动
        i, j = 0, 0
        result = 0
        while i < m:
            # > 注意：这里必须使用<=，防止两个heater设在同一个位置的老6情况，导致j指针停滞不前
            while abs(heaters[j + 1] - houses[i]) <= abs(heaters[j] - houses[i]):
                j += 1
            result = max(result, abs(heaters[j] - houses[i]))
            i += 1
        return result

4.执行结果