LeetCode 475. 供暖器

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为
标签
数组 排序 双指针 二分查找

题目描述

✅ 475. 供暖器

image-20260928224210058

image-20260928224210059

题意分析

房屋和供暖器位于一条直线上，所有供暖器使用相同的加热半径。每栋房屋只需落在至少一台供暖器的覆盖范围内，求能覆盖全部房屋的最小半径。

一台供暖器可以覆盖任意多栋房屋，不存在逐个配对或容量限制。因此每栋房屋可以独立选择离它最近的供暖器，再综合这些房屋各自的半径需求。

解法：排序 + 二分

核心思路

[!blue]

对一栋房屋来说，至少需要的半径就是它到最近供暖器的距离。把所有房屋的这个距离取最大值 R：半径小于 R，必然漏掉达到最大需求的房屋；半径等于 R，每栋房屋都能被自己的最近供暖器覆盖。所以这个最大值恰好是最优答案。

把供暖器位置排序，对当前房屋用下界二分查找第一个不小于它的位置 idx。左侧供暖器中，最靠右的 idx - 1 最近；右侧供暖器中，最靠左的 idx 最近，其余供暖器只会更远，因此只需比较这两个邻居。

下界二分维护半开区间 [left, right)。若 heaters[mid] >= house，答案可能就是 mid 或在它左侧，让 right = mid；否则 mid 及左侧都不够大，让 left = mid + 1。两端相遇时就是第一个满足条件的位置，也可能等于数组长度。

idx = 0 时只有右侧候选，idx = heaters.length 时只有左侧候选，其他情况取两侧距离的较小值。房屋恰好与供暖器重合时，这个最近距离自然为 0。

解题步骤

  1. 将 heaters 原地升序排序，答案初始化为 0。
  2. 对每栋房屋查找第一台位置不小于它的供暖器，得到下界 idx。
  3. 根据 idx 是否位于两端，计算现有左、右邻居的距离，取最近距离。
  4. 用该房屋的最近距离更新全局最大值。
  5. 返回最终半径。题目保证至少有一台供暖器，因此每栋房屋总有一侧候选可用。

代码实现

class Solution {
    // 将供暖器位置排序后，对任意房屋，最近供暖器只可能在插入位置的左侧或右侧。
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int answer = 0;

        for (int house : houses) {
            int idx = lowerBound(heaters, house);
            int distance;

            // 插入位置可能在两端，只访问实际存在的邻居
            if (idx == 0) {
                distance = heaters[0] - house;
            } else if (idx == heaters.length) {
                distance = house - heaters[heaters.length - 1];
            } else {
                int leftDistance = house - heaters[idx - 1];
                int rightDistance = heaters[idx] - house;

                distance = Math.min(leftDistance, rightDistance);
            }

            // 每栋先求最近距离，再取所有房屋的最大需求
            answer = Math.max(answer, distance);
        }

        return answer;
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

import "sort"

func findRadius(houses []int, heaters []int) int {
    // 将供暖器位置排序后，对任意房屋，最近供暖器只可能在插入位置的左侧或右侧。
    sort.Ints(heaters)
    answer := 0

    for _, house := range houses {
        idx := lowerBound475(heaters, house)
        distance := 0
        // 插入位置可能在两端，只访问实际存在的邻居
        if idx == 0 {
            distance = heaters[0] - house
        } else if idx == len(heaters) {
            distance = house - heaters[len(heaters)-1]
        } else {
            leftDistance := house - heaters[idx-1]
            rightDistance := heaters[idx] - house
            if leftDistance < rightDistance {
                distance = leftDistance
            } else {
                distance = rightDistance
            }
        }

        // 每栋先求最近距离，再取所有房屋的最大需求
        if distance > answer {
            answer = distance
        }
    }

    return answer
}

func lowerBound475(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

复杂度分析

  • 时间复杂度：$O((h+m)\log(h+1))$，h 为供暖器数、m 为房屋数。
  • 空间复杂度：查询部分 $O(1)$，另计供暖器排序的辅助空间。

关键点总结

[!green]

  • 每栋房屋对供暖器取最小距离，不同房屋之间再取最大需求。
  • 供暖器排序后，距离最近者只可能是下界位置及它的前驱。
  • 下界允许返回数组长度，这个哨兵位置表示所有供暖器都在房屋左侧。

易错点总结

[!yellow]

  • 下界可能为 0 或供暖器数量，需要先处理边界，不能直接同时访问 idx - 1 和 idx。
  • 只看左侧或只看右侧，可能漏掉另一侧更近的供暖器。
  • 不要把房屋与供暖器一一配对，同一台供暖器可以同时满足多栋房屋。
  • 全局答案取最大最近距离；取最小值只能保证某栋房屋被覆盖，不能保证全部房屋。

相似题目

题目 难度 关联与区别
35. 搜索插入位置 简单 排序供暖器后，对每所房子查下界及其前驱，即可找到最近供暖器。
849. 到最近的人的最大距离 中等 同样取到最近已占位置的距离，原题选择最远空座位，本题要让所有房子都覆盖，取各最近距离的最大值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/16728983
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！