题目分析

最近忙于论文，停更了一段时间，现在继续我们的刷题之旅。我们要寻找最小的加热半径，因为每一个房屋都需要加热到，因此我们找到距离每个房屋最近的供暖器到该房屋之间的距离，并求所有距离的最大值即可。

二分查找

这个题目有一个小技巧，为了方便二分查找对于边界值的讨论，我们可以在正无穷和负无穷远处加上两个供暖器，这样就不会超出边界，也不用对特殊值进行分类讨论。

算法的**时间复杂度为$O(mlog(n))$，空间复杂度为$O(1)$**，其中m为房屋个数，n为供暖器个数。

class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """
        heaters.append(float('inf'))
        heaters.append(-float('inf'))
        heaters.sort()
        max_dis = 0
        for h in houses:
            left, right = 0, len(heaters)
            while left < right:
                mid = (left + right) // 2
                if heaters[mid] >= h:
                    right = mid
                else:
                    left = mid + 1
            max_dis = max(max_dis, min(h - heaters[left - 1], heaters[left] - h))
        return max_dis

刷题总结

这个题目难度不大，但是往往第一眼看上去并没有思路，小伙伴们需要多见一些题目，这样才能迅速反应过来如何求解。