供暖器 | 徐年の博客

力扣 475. 供暖器

题目说明

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

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

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

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

提示：

1 <= houses.length, heaters.length <= 3 * 10^4
1 <= houses[i], heaters[i] <= 10^9

示例

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题中的每个房子使用的供暖不是前一个供暖器就是后一个，所以我们只需要遍历每个屋子并判断即可，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * TreeSet
     * 数组
     */
    public int findRadius(int[] houses, int[] heaters) {
        // 采用 TreeSet 来存储供暖器的位置，方便取得房屋前后取暖器的位置
        TreeSet<Integer> set = new TreeSet<>();
        int result = 0;

        for (int heater: heaters) {
            set.add(heater);
        }

        for (int house: houses) {
            // floor：取得当前 TreeSet 中小于等于当前元素的最大值
            Integer low = set.floor(house);
            // floor：取得当前 TreeSet 中大于等于当前元素的最小值
            Integer high = set.ceiling(house);

            if (low == null) {
                result = Math.max(result, high - house);
            }
            else if (high == null) {
                result = Math.max(result, house - low);
            }
            else {
                result = Math.max(result, Math.min((high - house), (house - low)));
            }
        }

        return result;
    }
}