LeetCode475-供暖器

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/heaters/

中文链接：https://leetcode-cn.com/problems/heaters/

题目详述

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

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

所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明:

  1. 给出的房屋和供暖器的数目是非负数且不会超过 25000。
  2. 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
  3. 只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
  4. 所有供暖器都遵循你的半径标准，加热的半径也一样。

示例 1:

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

示例 2:

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

题目详解

  • 每个房屋离最近的供暖器有一个最小距离，求的是所有最小距离的最大值。
  • 对供暖器进行排序。
  • 遍历房屋，对每个房屋找到距离它最近的两个供暖器（可能只存在一个），取两者较小值。
  • 并更新所有房屋最小距离的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00475 {

    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int res = 0;
        for (int x : houses) {
            int i = Arrays.binarySearch(heaters, x);
            if (i < 0) {
                i = ~i;
            }
            int dis1 = i > 0 ? x - heaters[i - 1] : Integer.MAX_VALUE;
            int dis2 = i < heaters.length ? heaters[i] - x : Integer.MAX_VALUE;
            res = Math.max(res, Math.min(dis1, dis2));
        }
        return res;
    }
}