[LeetCode] 475. Heaters

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater’s warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will the same.

Example 1:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

Example 3:
Input: houses = [1,5], heaters = [2]
Output: 3

Constraints:
1 <= houses.length, heaters.length <= 3 * 104
1 <= houses[i], heaters[i] <= 109

供暖器。

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/heaters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 双指针

首先是双指针的思路，两个指针是同向的，都是从左往右走。对于双指针的做法，需要对两个 input 数组都进行排序，这样当我们用两个指针去分别遍历 houses 数组和 heaters 数组的时候，对于每一个 house，我们要看到底是当前这个 heater 离得近还是下一个 heater 离得近，如果一直是下一个 heater 离得近则 heater 的指针一直往前走。

复杂度

时间O(mn) - 极端情况
空间O(1)

代码

Java实现

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int res = 0;
        int i = 0;
        for (int house : houses) {
            int dist = Math.abs(house - heaters[i]);
            // 如果下一个heater离得近，则i++
            while (i + 1 < heaters.length && Math.abs(house - heaters[i + 1]) <= Math.abs(house - heaters[i])) {
                i++;
                dist = Math.min(dist, Math.abs(house - heaters[i]));
            }
            res = Math.max(res, dist);
        }
        return res;
    }
}

思路二 - 二分答案 + 双指针

另一种思路是二分法。这里我们需要对 houses 和 heaters 分别排序。这里我们二分的是一个合理的半径。对于某个找到的半径，我们去试探，看是否这个半径能满足所有房屋的供暖。如果能满足，尽量移动右指针去缩小这个半径；如果不能满足，则移动左指针去增大这个半径。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int left = 0;
        int right = (int) Math.pow(10, 9) + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (helper(houses, heaters, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    private boolean helper(int[] houses, int[] heaters, int x) {
        int m = houses.length;
        int n = heaters.length;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            while (i < m && houses[i] >= heaters[j] - x && houses[i] <= heaters[j] + x) {
                i++;
            }
            j++;
        }
        if (i == m) {
            return true;
        }
        return false;
    }
}