题目分析
最近忙于论文,停更了一段时间,现在继续我们的刷题之旅。我们要寻找最小的加热半径,因为每一个房屋都需要加热到,因此我们找到距离每个房屋最近的供暖器到该房屋之间的距离,并求所有距离的最大值即可。
二分查找
这个题目有一个小技巧,为了方便二分查找对于边界值的讨论,我们可以在正无穷和负无穷远处加上两个供暖器,这样就不会超出边界,也不用对特殊值进行分类讨论。
算法的**时间复杂度为$O(mlog(n))$,空间复杂度为$O(1)$**,其中m为房屋个数,n为供暖器个数。
1 | class Solution(object): |
刷题总结
这个题目难度不大,但是往往第一眼看上去并没有思路,小伙伴们需要多见一些题目,这样才能迅速反应过来如何求解。