475. 供暖器

这道题我们可以采用贪心算法，每次找到离这个房屋的最短距离，最后求取最大值即可。首先可以先将heaters排序，这样可以方便使用二分查找，然后创建寻找最小距离的函数，每次传入房子所在的位置，在heaters中使用二分查找，找到离这个点最近的点，若是有则为0，若没有，则比较左边的和右边的哪个离得更近。返回更近的数值。参数引用要使用引用传递，不然会超内存。

class Solution { public: int findHeaters(const vector<int> &heaters,int n){ int left=0; int right=heaters.size()-1; if(n<heaters[0]){ return heaters[0]-n; } if(n>heaters[heaters.size()-1]){ return n-heaters[heaters.size()-1]; } while(left<=right){ int mid=left+(right-left)/2; if(heaters[mid]==n){ return 0; } else if(heaters[mid]>n){ right=mid-1; } else if(heaters[mid]<n){ left=mid+1; } } int res=min(n-heaters[left-1],heaters[left]-n); return res; } int findRadius(vector<int>& houses, vector<int>& heaters) { sort(heaters.begin(),heaters.end()); int ans=0; for(int i=0;i<houses.size();i++){ ans=max(findHeaters(heaters,houses[i]),ans); } return ans; } };