冬天来了,我们用算法来-供暖

在这里插入图片描述

求解思路

这道题的本质是为每个房屋找到最近的供暖器,然后在所有"房屋到最近供暖器的距离"中取最大值,这个最大值就是所要求的答案。

想象一下,如果我们把供暖半径设置为这个最大距离,那么所有房屋都能被覆盖;

如果半径比这个值小,就会有某个房屋无法被覆盖。

解题的关键在于如何高效地为每个房屋找到最近的供暖器,本文采用贪心策略:

先对房屋和供暖器的位置都排序,然后利用位置的单调性,用双指针的方式遍历,对于每个房屋,我们不断尝试下一个供暖器,如果下一个供暖器离当前房屋更远了,就说明当前供暖器是最优选择。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public static int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(houses);
    Arrays.sort(heaters);
    int ans = 0;
    
    for (int i = 0, j = 0; i < houses.length; i++) {
        // 为第i个房屋找最近的供暖器
        while (!best(houses, heaters, i, j)) {
            j++;
        }
        // 更新最大半径
        ans = Math.max(ans, Math.abs(heaters[j] - houses[i]));
    }
    return ans;
}

// 判断heaters[j]是否是houses[i]的最优供暖器
public static boolean best(int[] houses, int[] heaters, int i, int j) {
    // 如果j已是最后一个供暖器,或者当前供暖器比下一个更近
    return j == heaters.length - 1 
            || Math.abs(heaters[j] - houses[i]) < Math.abs(heaters[j + 1] - houses[i]);
}

如果觉得有帮助，欢迎点赞、关注、转发~