475.供暖器

原题

最小的最大

全局最小的加热半径, 等于所有房屋到最近加热器的距离中的最大值。

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        #先将房屋和供暖器排序
        houses.sort()
        heaters.sort()
        # 辅助
        heaters.insert(0, -sys.maxsize)
        heaters.append(sys.maxsize)

        res = 0	#结果
        m = len(houses)
        n = len(heaters)
        cur = 0
        # 核心思路:用双指针cur指示供暖器,i指示房屋,当 heaters[cur] >= houses[i] 时
        # cur和cur-1就是房屋左右两侧最近的供暖器下标
        # 比较左右哪个更近,较小值则为房屋与供暖器距离dis
        # 再用dis与res比较,取较大值为res
        # 注意cur=0时,cur-1越界; 或cur-1=n-1时,cur越界,因此需要在两端加一个辅助供暖器,但不使用
        for i in range(m):
            while cur < n:
                if heaters[cur] >= houses[i]:
                    break
                cur += 1
		   # 求最小距离
            dis = min(heaters[cur] - houses[i], houses[i] - heaters[cur-1])
            #更新
            res = max(res, dis)
        return res