思路排序 双指针对每个房子只需要找到离它最近的供暖器然后记录所有房子到其最近供暖器距离的最大值就是需要的最小加热半径。关键观察把 houses 和 heaters 都排序后可以用双指针线性扫描· 指针 j 指向第一个位置 当前房子的供暖器· 对当前房子最近供暖器只可能是 heaters[j-1]左边或 heaters[j]右边· 因为 houses 递增j 也只会单调递增不会回退。Java 实现importjava.util.Arrays;classSolution{publicintfindRadius(int[]houses,int[]heaters){Arrays.sort(houses);Arrays.sort(heaters);intans0;intj0;// j 指向第一个 当前房子的供暖器for(inthouse:houses){// 向右推进 j直到 heaters[j] house 或越界while(jheaters.lengthheaters[j]house){j;}// 右边候选供暖器intright(jheaters.length)?heaters[j]-house:Integer.MAX_VALUE;// 左边候选供暖器intleft(j0)?house-heaters[j-1]:Integer.MAX_VALUE;ansMath.max(ans,Math.min(left,right));}returnans;}}代码说明· 排序houses 和 heaters 都要排序才能用双指针找到左右最近的供暖器· j 不回退因为 house 单调递增第一个 house 的供暖器下标也只会越来越大所以整个循环 j 最多走 heaters.length 次· 左右候选heaters[j] 是右侧最近的heaters[j-1] 是左侧最近的取两者距离较小值作为该房子的最近距离· 边界处理若 j 0 表示没有左侧供暖器left MAX_VALUE若 j heaters.length 表示没有右侧供暖器right MAX_VALUE· 最终 ans 是所有房子最近距离的最大值。复杂度· 时间复杂度O(n log n m log m)主要来自排序扫描部分为 O(n m)。· 空间复杂度O(log n log m)排序递归栈开销。另一种写法二分查找importjava.util.Arrays;classSolution{publicintfindRadius(int[]houses,int[]heaters){Arrays.sort(heaters);intans0;for(inthouse:houses){// 找第一个 house 的供暖器下标intidxlowerBound(heaters,house);intright(idxheaters.length)?heaters[idx]-house:Integer.MAX_VALUE;intleft(idx0)?house-heaters[idx-1]:Integer.MAX_VALUE;ansMath.max(ans,Math.min(left,right));}returnans;}// 返回第一个 target 的下标privateintlowerBound(int[]arr,inttarget){intlo0,hiarr.length;while(lohi){intmidlo(hi-lo)/2;if(arr[mid]target)lomid1;elsehimid;}returnlo;}}二分写法对每个房子做一次 O(log m) 查找总复杂度 O(n log m m log m)稍慢于双指针但同样正确且好理解。易错点j 不能对每个房子重置为 0否则退化为 O(n * m)会超时由于 houses 已排序j 单调递增即可while 条件用 house 而不是 house这样 j 停在第一个 house 的位置方便取左右候选若用 需相应调整左右指针逻辑空数组边界j 0 或 j heaters.length 时另一侧候选应设为 Integer.MAX_VALUE取 min 自然被忽略答案累加用 Math.max题意是覆盖所有房屋的最小半径即每个房子都要被覆盖所以取所有房子最近距离的最大值。
