Medium

题目描述

冬天来了！在比赛期间，你的第一个任务是设计一个有固定加热半径的标准供暖器来供暖所有房屋。

每个房屋都可以被供暖，只要房屋在供暖器的加热半径范围内。

给定房屋和供暖器在水平线上的位置，返回供暖器的最小加热半径标准，使得这些供暖器能够覆盖所有房屋。

请注意，所有供暖器都遵循你的半径标准，加热半径将是相同的。

示例 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

提示：

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

解题思路

这个问题的核心思路是：要使所有房屋都能被供暖，需要找到使最远距离房屋也能被覆盖的最小半径。

对于每个房屋，我们需要找到距离它最近的供暖器，然后取所有房屋到其最近供暖器距离的最大值。

主要解法思路：

  1. 排序 + 双指针法（推荐）：先对两个数组排序，然后对每个房屋使用双指针找到最近的供暖器。时间复杂度较低。

  2. 排序 + 二分查找法：对供暖器数组排序，然后对每个房屋使用二分查找找到最近的供暖器位置。

具体步骤：

  • 首先对供暖器数组排序
  • 对于每个房屋，找到离它最近的供暖器距离
  • 对于房屋位置 house，最近供暖器要么在它左边，要么在它右边
  • 使用二分查找找到第一个大于等于房屋位置的供暖器索引
  • 比较该位置和前一个位置的供暖器距离，取较小值
  • 所有房屋中的最大距离就是答案

代码实现

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(heaters.begin(), heaters.end());
        int radius = 0;
        
        for (int house : houses) {
            int pos = lower_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
            int minDist = INT_MAX;
            
            // 检查右边的供暖器
            if (pos < heaters.size()) {
                minDist = min(minDist, heaters[pos] - house);
            }
            
            // 检查左边的供暖器
            if (pos > 0) {
                minDist = min(minDist, house - heaters[pos - 1]);
            }
            
            radius = max(radius, minDist);
        }
        
        return radius;
    }
};

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        heaters.sort()
        radius = 0
        
        for house in houses:
            pos = bisect.bisect_left(heaters, house)
            min_dist = float('inf')
            
            # 检查右边的供暖器
            if pos < len(heaters):
                min_dist = min(min_dist, heaters[pos] - house)
            
            # 检查左边的供暖器
            if pos > 0:
                min_dist = min(min_dist, house - heaters[pos - 1])
            
            radius = max(radius, min_dist)
        
        return radius

public class Solution {
    public int FindRadius(int[] houses, int[] heaters) {
        Array.Sort(heaters);
        int radius = 0;
        
        foreach (int house in houses) {
            int pos = Array.BinarySearch(heaters, house);
            if (pos < 0) pos = ~pos;
            
            int minDist = int.MaxValue;
            
            // 检查右边的供暖器
            if (pos < heaters.Length) {
                minDist = Math.Min(minDist, heaters[pos] - house);
            }
            
            // 检查左边的供暖器
            if (pos > 0) {
                minDist = Math.Min(minDist, house - heaters[pos - 1]);
            }
            
            radius = Math.Max(radius, minDist);
        }
        
        return radius;
    }
}

var findRadius = function(houses, heaters) {
    heaters.sort((a, b) => a - b);
    let radius = 0;
    
    for (let house of houses) {
        let left = 0, right = heaters.length - 1;
        
        // 二分查找第一个大于等于house的位置
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (heaters[mid] < house) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        let minDist = Infinity;
        
        // 检查右边的供暖器
        if (left < heaters.length) {
            minDist = Math.min(minDist, heaters[left] - house);
        }
        
        // 检查左边的供暖器
        if (left > 0) {
            minDist = Math.min(minDist, house - heaters[left - 1]);
        }
        
        radius = Math.max(radius, minDist);
    }
    
    return radius;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log m + m log m)，其中 n 是房屋数量，m 是供暖器数量
空间复杂度O(1)，除了排序所需的额外空间