该题目简而言之,就是找出每个house的min heater(距离最近的heater),算出radius(半径),再找出所有house对应的radius中的最大值,即为标准供热半径。
binary search可以找出有序数组中需要查找的数字
简单举例: houses[14] heaters[1,8,10,20,32] 只有一间屋子,位于14这个位置,左侧最近的heater位于10,右侧最近的heater位于20,min(14-10,20,14)=4,所以14这件屋子需要供热的话,radius=4即可 (这是最基本的思路)
下述算法给出的是对基本算法略微改进的算法,希望读者在基本思路的基础上去理解下述算法。
新闻热点
疑难解答