475-供暖器

LeetCode 475. 供暖器

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

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

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

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

示例 1:

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

示例 2:

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

示例 3：

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

method 1: 二分+贪心+双指针

check的逻辑

• 要找到第一个右边界大于当前房屋的供暖器
• 找到后还要看看房屋的位置是不是小于于供暖器的左边界

bool check(int r, vector<int>& houses, vector<int>& heaters) {
    int m = houses.size(), n = heaters.size();
    for (int i = 0, j = 0; i < m; i++) {
        while (j < n && houses[i] > heaters[j] + r) j++;	// 找到满足右边界的
        if (j == n || houses[i] < heaters[j] - r) return false;	// 检验左边界是否满足
    }
    return true;
}
int findRadius(vector<int>& houses, vector<int>& heaters) {
    sort(houses.begin(), houses.end());
    sort(heaters.begin(), heaters.end());
    int l = 0, r = INT_MAX;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid, houses, heaters)) r = mid;
        else l = mid + 1;
    }
    return r;
}

时间复杂度：$O(max(m, n) * logL)$，其中$L$是供暖的最大范围
空间复杂度：$O(logm + logn)$，排序需要的栈空间

method 2: 排序+二分

• 先对供暖器进行排序
• 分别对每个房屋执行这样的策略：找到距离房屋的最近的左右两个供暖器，计算左右半径，取较小值
• 每个房屋的最小半径取最大值

注意越界的处理，可能房屋没有对应的左边或右边的供暖器

int findRadius(vector<int>& houses, vector<int>& heaters) {
    sort(heaters.begin(), heaters.end());
    int res = 0;
    for (auto house : houses) {
        int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin();   // 第一个大于house的位置
        int i = j - 1;  // house的左边的供暖器
        int right = j == heaters.size() ? INT_MAX : heaters[j] - house;
        int left = i == -1 ? INT_MAX : house - heaters[i];
        int r = min(right, left);   // 左右取较小值
        res = max(res, r);  // 每个房屋的最小半径取最大值
    }
    return res;
}