475. 供暖器

题目描述

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

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

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

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

说明

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

示例

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

输入：houses = [1,5], heaters = [2]
输出：3

暴力解法

分析：排序后从左开始遍历每一个房屋，求每个房屋到最近供暖器的距离，然后找出最大的值。
求每个房屋到最近供暖器的距离：相邻的左边供暖器和右边供暖器距离里取小的值。

func findRadius(houses []int, heaters []int) int {
	var (
		radius int
		i      int
		j      int
	)
	// sort
	sort.Ints(houses)
	sort.Ints(heaters)
	t := 0
	for j = 0; j < len(houses); j++ {
		tmp := 0
		for i = t; i < len(heaters); i++ {
			if heaters[i] < houses[j] {
				tmp = houses[j] - heaters[i]
			} else if tmp != 0 {
				tmp = int(math.Min(float64(tmp), float64(heaters[i]-houses[j])))
				if i != 0 {
					t = i - 1
				}
				break
			} else {
				tmp = heaters[i] - houses[j]
				if i != 0 {
					t = i - 1
				}
				break
			}
		}
		radius = int(math.Max(float64(radius), float64(tmp)))
	}
	return radius
}

本地测试

package main

import (
	"fmt"
)

func main() {
	var a, b []int
	a = []int{1, 2, 3}
	b = []int{2}
	fmt.Println(findRadius(a, b))

	a = []int{1, 2, 3, 4}
	b = []int{1, 4}
	fmt.Println(findRadius(a, b))

	a = []int{1, 5}
	b = []int{2}
	fmt.Println(findRadius(a, b))

	a = []int{282475249, 622650073, 984943658, 144108930, 470211272, 101027544, 457850878, 458777923}
	b = []int{823564440, 115438165, 784484492, 74243042, 114807987, 137522503, 441282327, 16531729, 823378840, 143542612}
	fmt.Println(findRadius(a, b))
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/heaters