0475. Heaters ============= 题目信息 -------- :题号: 0475 :难度: Medium :主题: 一维位置、统一半径、房屋覆盖、最小可行半径 :原题: `LeetCode 0475 `_ :重点: 每个加热器左右覆盖相同半径、所有加热器共用同一个半径、每座房屋至少被一个加热器覆盖 题目重述 -------- 一条水平线上有若干房屋和加热器,它们的位置分别由整数数组 ``houses`` 和 ``heaters`` 给出。为所有加热器设置同一个非负覆盖半径 ``r``;位置为 ``h`` 的加热器能够覆盖闭区间 ``[h-r, h+r]``。 返回能够覆盖全部房屋的最小半径。房屋或加热器位置可以按任意顺序给出。两个数组长度均位于 ``[1, 3 * 10^4]``,位置位于 ``[1, 10^9]``。每座房屋只需落在至少一个加热器的覆盖范围内。 自建示例 -------- 中间房屋决定最小半径: .. code-block:: text 输入:houses = [1,5,9],heaters = [2,8] 输出:3 解释:房屋 1 和 9 距最近加热器均为 1,房屋 5 距两个加热器都为 3,因此统一半径至少为 3。 房屋与加热器位置相同: .. code-block:: text 输入:houses = [4],heaters = [4] 输出:0 解释:房屋正好位于加热器位置,不需要向外扩展覆盖范围。 每座房屋取最近加热器的距离 -------------------------- 固定半径 ``r`` 时,一座房屋能否被覆盖只取决于它到最近加热器的距离。因此对每座房屋寻找左右两侧最近的加热器,取两者距离的较小值;所有房屋所需距离的最大值,就是统一半径的最小可行值。 排序加热器后用 ``lower_bound`` 定位第一个不小于房屋位置的加热器,同时检查它和前一个位置。边界只有一侧候选时,将另一侧视为无穷远。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findRadius(std::vector& houses, std::vector& heaters) { std::sort(heaters.begin(), heaters.end()); long long answer = 0; for (int house : houses) { auto rightIt = std::lower_bound(heaters.begin(), heaters.end(), house); long long right = rightIt == heaters.end() ? LLONG_MAX : static_cast(*rightIt) - house; long long left = rightIt == heaters.begin() ? LLONG_MAX : house - static_cast(*std::prev(rightIt)); answer = std::max(answer, std::min(left, right)); } return static_cast(answer); } }; 代码分析 -------- 最近加热器必然是排序位置中房屋左右相邻的两个候选之一,检查这两个位置即可得到该房屋的最小覆盖半径;再取所有房屋的最大需求保证全部覆盖。排序耗时 ``O(h log h)``,每座房屋二分耗时 ``O(log h)``,总时间复杂度为 ``O(h log h + r log h)``,额外空间复杂度为 ``O(1)``。