475.供暖器

题目描述

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。
示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。
示例 3：

输入：houses = [1,5], heaters = [2]
输出：3

题解

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        /*
 * 核心思路：排序 + 双指针 (贪心)
 * * 1. 【预处理 - 排序】：
 * 首先将 houses 和 heaters 排序。
 * 这是使用双指针的前提：保证房屋和供暖器都是从左到右分布的，
 * 这样我们寻找“最近供暖器”时就不需要回头看。
 * * 2. 【寻找最近的供暖器 - 贪心策略】：
 * - 对于当前的房子 houses[i]，我们需要在 heaters 中找到离它最近的那个。
 * - 我们维护一个指针 j 指向当前的供暖器。
 * - 核心决策（while 循环）：
 * 判断“当前的供暖器 heaters[j]”和“下一个供暖器 heaters[j+1]”，
 * 哪一个离房子 houses[i] 更近？
 * - 如果下一个 heaters[j+1] 更近，说明 j 已经“过时”或者是“太左边”了，
 * 我们就让 j 向右移动 (j++)，去尝试下一个。
 * - 否则，说明 heaters[j] 就是当前房子 i 能找到的最近的供暖器，停止移动。
 * * 3. 【优化的关键 - 不回退】：
 * - 注意 j 是定义在 for 循环外部的。
 * - 当我们需要为下一栋房子 houses[i+1] 找供暖器时，
 * 因为 houses[i+1] 一定在 houses[i] 的右边（已排序），
 * 所以它的最近供暖器不可能在 heaters[j] 的左边。
 * - 因此 j 不需要重置为 0，而是接着上一次的位置继续往右找。
 * - 这使得时间复杂度从 O(N*M) 降低到了 O(N + M)（忽略排序时间）。
 * * 4. 【最终结果】：
 * - 每一栋房子都有一个“最小供暖半径”（即它到最近供暖器的距离）。
 * - 为了覆盖所有房子，我们需要满足那个“最难覆盖”的房子。
 * - 所以结果是所有房子最小半径中的的最大值 (Max of Mins)。
 */
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ans = 0;
        for(int i = 0,j = 0;i<houses.length;i++){
            while(!best(houses,heaters,i,j)){
                j++;
            }
            ans = Math.max(ans,Math.abs(houses[i]-heaters[j]));
        }
        return ans;
    }

    public boolean best(int[] houses,int[] heaters,int i,int j){
        return j == heaters.length - 1
                        ||
            Math.abs(houses[i]-heaters[j]) < Math.abs(houses[i]-heaters[j+1]);
    }
}