供暖器

标签: 数组 双指针 二分查找 排序

难度: Medium

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

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

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

注意：所有供暖器 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

提示：

  • 1 <= houses.length, heaters.length <= 3 * 104
  • 1 <= houses[i], heaters[i] <= 109

Submission

运行时间: 61 ms

内存: 19.0 MB

"""
Question:
    Given 2 list[int] representing the positions of houses and heaters,
    design a minimum fixed radius s.t. all heaters can warm all houses.
Input:
    list[int]: houses
    list[int]: heaters
Return:
    int: minimum redius
Constraints:
    - 1 <= m, n <= 3 8 10^4
Idea:
1. 2 pointers:
sort the houses and heaters,
go through houses to find the minimum radius house -> radius
pick the max radius from all min radius for each house
[1,2,3,4]
       ^
[1,4]
   ^
[0,1,1,0] -> 1
"""


class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        m, n = len(houses), len(heaters)
        houses = sorted(houses)
        heaters = sorted(heaters)
        ans = 0
        # i point to heaters
        i = 0
        for house in houses:
            radius = abs(house - heaters[i])
            # check next heater
            while i + 1 < n and abs(heaters[i+1] - house) <= radius:
                i += 1
                radius = abs(heaters[i] - house)
            # update min global radius
            ans = max(ans, radius)
        return ans

Explain

该题解采用双指针的思路。首先将房屋位置和供暖器位置分别进行排序。然后遍历每个房屋，对于每个房屋，找到能够覆盖该房屋的供暖器，并计算所需的最小加热半径。在遍历房屋的过程中，通过移动供暖器的指针，找到与当前房屋最近的供暖器，并更新该房屋所需的最小加热半径。最终，在所有房屋所需的最小加热半径中取最大值，即为可以覆盖所有房屋的最小加热半径。

时间复杂度: O(mlogm + nlogn)

空间复杂度: O(m + n)

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        m, n = len(houses), len(heaters)
        houses = sorted(houses)  # 对房屋位置进行排序
        heaters = sorted(heaters)  # 对供暖器位置进行排序
        ans = 0
        i = 0  # 供暖器的指针
        for house in houses:
            radius = abs(house - heaters[i])  # 计算当前房屋与当前供暖器之间的距离
            # 如果下一个供暖器存在且与当前房屋的距离更近，则移动供暖器指针
            while i + 1 < n and abs(heaters[i+1] - house) <= radius:
                i += 1
                radius = abs(heaters[i] - house)
            ans = max(ans, radius)  # 更新最小加热半径
        return ans

Explore

在这个问题中，两个数组（房屋和供暖器）各自代表不同的实体和属性，房屋和供暖器的位置是独立的并且它们的数量可以不同。使用两个指针分别遍历两个不同的数组允许我们在每个房屋位置独立地查找最接近的供暖器，从而有效地计算出所需的最小加热半径。如果在同一个数组内使用两个指针，我们将无法实现这种独立的匹配和最小距离的计算，因为这需要同时参照两个不同属性的集合。

算法通过保持一个指针在供暖器数组上移动，并且只在找到一个更近的供暖器时才向前移动该指针来实现。这种方法确保了我们不会回退指针，只在确认下一个供暖器距离当前房屋更近时才移动，由此避免错过任何可能的更近供暖器。同时，供暖器和房屋数组事先已经被排序，这保证了供暖器的指针总是向前移动，从而可以一次性遍历完成且不遗漏。

在所有供暖器都位于所有房屋的一侧这样的边界情况下，算法仍然有效，因为供暖器和房屋已经排序，算法会计算每个房屋到其最近供暖器的距离。即使所有供暖器都在房屋的一侧，指针移动依然能够找到每个房屋相对最近的供暖器，并计算出所需的加热半径。最终，算法取所有房屋所需加热半径的最大值，确保所有房屋都能被有效覆盖。

尽管供暖器的数量远少于房屋的数量，该算法的效率仍然是高效的。因为每个房屋只需要找到最近的一个供暖器，供暖器的指针只在有必要时才向前移动，从而避免了不必要的重复计算。算法的时间复杂度主要由房屋的数量决定，即O(m)，其中m是房屋的数量。供暖器指针的移动总次数不会超过供暖器的数量n，因此整体的时间复杂度为O(m + n)，在供暖器数量远少于房屋的情况下，这仍然是有效的。