供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

  • 输入: houses = [1,2,3], heaters = [2]

  • 输出: 1

  • 解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。

  • 输入: houses = [1,2,3,4], heaters = [1,4]

  • 输出: 1

  • 解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var findRadius = function(houses, heaters) {
    heaters = [...heaters.sort((a, b) => a - b)]
    let res = 0
    for (const home of houses) {
        let left = 0
        let right = heaters.length - 1
        let mid;
        let ans = Math.abs(home - heaters[0]);
        if(home < heaters[left]){
            ans = heaters[left] - home;
        }else if (home>heaters[right]){
            ans = home-heaters[right]
        }else{
            while (left < right) {
                mid = left + ((right - left) >> 1)
                if (right - left === 1) {
                    ans = Math.min(home - heaters[left], heaters[right] - home);
                    break;
                }else if (heaters[left+1]>home) {
                    ans = Math.min(home - heaters[left], heaters[left+1] - home);
                    break;
                }else if(heaters[right-1]<home){
                    ans = Math.min(home - heaters[right-1], heaters[right] - home);
                    break;
                }
                if (heaters[mid] < home) {
                    left = mid;
                } else if(heaters[mid] > home) {
                    right = mid;
                } else {
                    ans = 0;
                    break;
                }
            }
        }
        res = Math.max(res, ans);
    }
    return res;
};