LeetCode 475. Heaters

Problem

LeetCode 475. Heaters

1. 题目简述

给出两个数组houses和heaters，houses是房子摆放的位置，heaters是加热器摆放的位置，注意，heaters的值不一定是houses里的值！！！求一个最小的加热半径radius，使得所有的房子都可以得到供暖。

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 heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

2. 算法思路

这道题属于二分搜索的普通应用，确定好，我们的目的是找到一个满足要求的最小的radius，因此，是求左边界。

这里需要注意的是check函数里面，判断是否能够heat的逻辑比较麻烦一点点，这里是一个个house进行判断的，由于两个数组的单调性，我们可以保证二者的关系是单调的，后面house能够被heat的heater绝不会小于前一个house的。

代码如下：

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        
        // 这里使用二分法，l = 0, r = 取heater和house的最大值
        int l = 0, r = Math.max(houses[houses.length - 1], heaters[heaters.length - 1]);
        
        while (l < r) {
            int mid = (l + r) / 2;
            if (canHeatAll(houses, heaters, mid)) {
                // 这里是找左边界
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    
    public boolean canHeatAll (int[] houses, int[] heaters, int radius) {
        // 这里的逻辑是保证了heaters和houses都是单调的，从前向后遍历的时候可以保证heater的下标永远<=house的下标
        for (int i = 0, j = 0; i < houses.length; i++) {
            while (j < heaters.length && Math.abs(houses[i] - heaters[j]) > radius) {
                // 说明当前的heater无法覆盖当前的house，这个写法思路很巧妙！！！
                j++;
            }
            
            if (j == heaters.length) {
                return false;
            }
        }
        
        return true;
    }
}