题目链接：供暖器
题目描述：
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
思路一
最暴力的做法：从半径1开始尝试，每次递增1，一直尝试到可以覆盖所有house
思路二
发现规律：最小半径一定是刚刚好可以覆盖所有house，所以最后求出的最小半径，一定是某个house与某个heater的距离。
基于此规律，提出思路二：
枚举所有house与heater的距离，使用TreeSet从小到大排序并去重，再逐个尝试，直到满足条件
思路三
思路二超时的主要原因，是house和heater的数量很多时，枚举所有house与heater的距离并排序和去重这一步骤相当耗时，如果可以每列出一个可能的距离，就尝试，直到满足条件，类似于懒加载，就可以省去提前枚举所有可能的开销。
但是又有了新的问题，如果不枚举所有可能并排序，怎么保证当前求出的距离就是最小半径？
基于此问题，提出思路三：
1.对所有的house和heater从小到大排序
2.遍历所有heater，对每一个heater，遍历所有house
3.设当前遍历到的house为houses[j]
计算houses[j]与当前heater以及下一个heater的距离，比较house与哪一个heater更近
如果houses[j]与下一个heater更近，跳出当前heater所在循环，看下一个heater
如果houses[j]与当前heater更近，就把house与当前heater的距离，作为一个可能的最小半径，判断该半径是否能覆盖所有house，如果可以，该半径就是答案，结束计算
步骤3的理论支持在于：
当前heater是距离houses[j]最近的heater，如果要覆盖houses[j]，最小半径肯定是当前heater与houses[j]的距离，其余heater与houses[j]的距离只可能更大。
因此，最后的最小半径不可能小于当前heater与houses[j]的距离，否则就没有任何一个heater可以覆盖houses[j]。
所以，如果以当前heater与houses[j]的距离作为半径，可以满足条件，那么该半径就可以作为最小半径
思路四
思路三中，对每一个heater，遍历所有house，找到可能的最小半径并尝试。
这一步骤存在冗余的计算，因为只有当house与当前遍历到的heater最近的时候，才会计算house与当前heater的距离。
也就是说，参与过计算的house，一定是离前面的heater近，离后面的heater远，对于这些house，无需计算与后面的heater的距离，因为house一定是被更近的heater覆盖
因此提出思路四：
基于思路三，对思路三的步骤2做出优化：对每一个heater，只遍历未参与过计算的house，其余步骤不变
思路五
思路四（即优化后的思路三）中，找到一个可能的最小半径并尝试时，具体的尝试步骤为：
1.遍历所有house，对每一个house，遍历所有heater，判断house是否在heater的覆盖范围内
2.如果当前heater无法覆盖house，就看下一个heater
3.如果house可以被任意一个heater覆盖，说明当前半径可以覆盖到当前house，跳出循环，看下一个house
步骤1中，只有当当前heater无法覆盖house时，才会看下一个heater，举个例子：
假设heaters[0]到heaters[3]都无法覆盖house[0]，直到heaters[4]才可以覆盖，
那么，对于house[1]，其实无需遍历所有heater，从heaters[4]开始尝试即可，
因为，相比house[0]，house[1]离heaters[0]到heaters[3]更远，如果heaters[0]到heaters[3]无法覆盖house[0]，那更不可能覆盖house[1]
因此提出思路五：
基于思路四，对尝试可能的最小半径时的步骤做出优化：对每一个house，只遍历未参与过计算的heater，其余步骤不变
最终AC代码如下，耗时527 ms（优化那么多次还是这么慢，好悲伤~）
class Solution {
public int findRadius(int[] houses, int[] heaters) {
// 从小到大排序
Arrays.sort(houses);
Arrays.sort(heaters);
// 最小半径一定是某个house与某个heater之间的距离，即刚刚好能覆盖
// 所以先从小到大算出所有可能的最小半径（剪枝），再一一遍历看是否满足条件
// 使用Set去重
Set<Integer> set = new HashSet<>();
// 已经计算过的house不再参与计算，所以j放外面
int j = 0;
for (int i = 0; i < heaters.length; i++) {
for (; j < houses.length; j++) {
// 半径
int radius = Math.abs(houses[j] - heaters[i]);
if (set.contains(radius)) {
continue;
}
// 如果当前house的位置离下一个heater更近，跳出循环
if (i < heaters.length - 1 && Math.abs(houses[j] - heaters[i + 1]) < radius) {
break;
}
// 判断当前半径是否满足条件
boolean success = true;
// 如果前i个heater都不能覆盖当前house，那么下一个house也不用考虑前i个heater，因为下一个house离前i个heater更远，所以k放外面
int k = 0;
for (int house: houses) {
// 当前house是否能被任意一个heater覆盖
boolean covered = false;
for (; k < heaters.length; k++) {
if (house >= heaters[k] - radius & house <= heaters[k] + radius) {
covered = true;
// 当前heater满足当前house，看下一个house
break;
}
}
// 任意一个house不能被所有heater覆盖，看下一个半径
if (!covered) {
success = false;
break;
}
}
if (success) {
return radius;
}
set.add(Math.abs(houses[j] - heaters[i]));
}
}
return -1;
}
}
网友评论