每日一题——475. 供暖器

475. 供暖器

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

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

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

说明:所有供暖器都遵循你的半径标准,加热的半径也一样

public class Solution {
    public int FindRadius(int[] houses, int[] heaters) {
        Array.Sort(heaters);
        Array.Sort(houses);
        int r = 0;
        for(int i = 0, j = 0;i < houses.Length; i++)
        {
            int maxLength = Math.Abs(houses[i] - heaters[j]);
            while(j < heaters.Length-1 && //后面有+1所以这里要-1
                    Math.Abs(houses[i] - heaters[j]) >=
                    Math.Abs(houses[i] - heaters[j+1])            
                 )
                {
                    //对于每个房屋,要么用前面的暖气要么用后面的,谁近取谁
                    //所有房屋遍历一遍,最大的距离就是暖气最小半径
                    j++;
                    maxLength = Math.Min(maxLength,Math.Abs(houses[i] - heaters[j]));
                }
            r = Math.Max(r, maxLength);
        }
        return r;
    }
}

注意:房子和取暖器的数量都不止一个,也不止两个

单个取暖器的情况很好想

主要是多个取暖器的时候怎么办

我在评论区看到的两点思路觉得很好的概括了这道题的解法

对于每个房屋来说,要么用前面的暖气(左侧)要么用后面的暖气(右侧)

谁比较近就取谁,如果这一组暖气不满足就下一组,一轮过后一定能找出最近的暖气

对于所有房屋来说,每个房屋的暖气的最近距离的最大值就是暖气的最小半径

只要明确了这两点就好做了

发表评论

您的电子邮箱地址不会被公开。