DeepSeek LeetCode 475. 供暖器 Java实现

思路：排序 + 双指针

对每个房子，只需要找到离它最近的供暖器，然后记录所有房子到其最近供暖器距离的最大值，就是需要的最小加热半径。

关键观察：把 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);intans=0;intj=0;// j 指向第一个 >= 当前房子的供暖器for(inthouse:houses){// 向右推进 j，直到 heaters[j] >= house 或越界while(j<heaters.length&&heaters[j]<house){j++;}// 右边候选供暖器intright=(j<heaters.length)?heaters[j]-house:Integer.MAX_VALUE;// 左边候选供暖器intleft=(j>0)?house-heaters[j-1]:Integer.MAX_VALUE;ans=Math.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);intans=0;for(inthouse:houses){// 找第一个 >= house 的供暖器下标intidx=lowerBound(heaters,house);intright=(idx<heaters.length)?heaters[idx]-house:Integer.MAX_VALUE;intleft=(idx>0)?house-heaters[idx-1]:Integer.MAX_VALUE;ans=Math.max(ans,Math.min(left,right));}returnans;}// 返回第一个 >= target 的下标privateintlowerBound(int[]arr,inttarget){intlo=0,hi=arr.length;while(lo<hi){intmid=lo+(hi-lo)/2;if(arr[mid]<target)lo=mid+1;elsehi=mid;}returnlo;}}

二分写法对每个房子做一次 O(log m) 查找，总复杂度 O(n log m + m log m)，稍慢于双指针，但同样正确且好理解。

易错点

1. j 不能对每个房子重置为 0：否则退化为 O(n * m)，会超时；由于 houses 已排序，j 单调递增即可；
2. while 条件用 < house 而不是 <= house：这样 j 停在第一个 >= house 的位置，方便取左右候选；若用 <=，需相应调整左右指针逻辑；
3. 空数组边界：j == 0 或 j == heaters.length 时，另一侧候选应设为 Integer.MAX_VALUE，取 min 自然被忽略；
4. 答案累加用 Math.max：题意是"覆盖所有房屋"的最小半径，即每个房子都要被覆盖，所以取所有房子最近距离的最大值。