暖气器问题这类算法题,看似简单,边界条件一踩就容易炸。我现场翻了半天代码才把温度覆盖范围算准——因为题里明明说了每个暖气器都有固定加热半径,但我第一眼就想着直接全局循环,结果 test case 一跑就超时。
核心是这样的:房子每个位置都有一个目标温度,要放置若干暖气器,每个暖气器加热一个固定范围的房间。问最少加热半径使得所有房间都能达到温度。Go 写法,咱先用二分查找半径:
package mainimport ("fmt""math""sort")funcminHeaterRadius(houses []int, heaters []int)int { sort.Ints(houses) sort.Ints(heaters) left, right := 0, 1_000_000_000for left < right { mid := (left + right) / 2if canCover(houses, heaters, mid) { right = mid } else { left = mid + 1 } }return left}funccanCover(houses []int, heaters []int, radius int)bool { i := 0for _, h := range heaters {// 每个暖气器覆盖区间 [h-radius, h+radius]for i < len(houses) && houses[i] <= h+radius {if houses[i] < h-radius {returnfalse } i++ } }return i == len(houses)}funcmain() { houses := []int{1,2,3,4,5} heaters := []int{1,4} fmt.Println(minHeaterRadius(houses, heaters)) // 输出最小半径}
这个地方我当时踩坑的是 canCover。第一版我没排序,数组一乱,覆盖判定直接炸。后来加了 sort.Ints,再用指针扫房子,复杂度就降下来。Go 里指针扫数组比 map 查找快得多,尤其是边界条件要特别注意:房子可能正好在两个暖气器中间,判断 < h-radius 和 <= h+radius 的边界差一个符号就全错。
另外,我发现题目里有些测试用例会让半径恰好是整数边界,比如房间 1,暖气器 4,你算出来 2.5 会被 round down,直接就覆盖失败。所以二分边界一定要用整数版本,left, right 初始值选大一点,保证覆盖全场景。
现场感的另一点是,很多人会直接用 for 嵌套 for 算每个房子到每个暖气器的距离,然后找最小值。Go 实测大数据 N=1e5 直接超时。我的经验是,先排序,然后线性扫一遍,复杂度从 O(N*M) 降到 O(N+M),再加二分,perf 就稳了。
还可以用另一种技巧:预处理房子左右最近的暖气器距离,取最大值就是半径。Go 写起来像这样:
funcminRadiusAlt(houses []int, heaters []int)int { sort.Ints(houses) sort.Ints(heaters) n := len(heaters) res := 0for _, h := range houses { idx := sort.Search(n, func(i int)bool { return heaters[i] >= h }) dist := math.MaxInt32if idx < n { dist = heaters[idx] - h }if idx > 0 { dist = min(dist, h - heaters[idx-1]) } res = max(res, dist) }return res}funcmin(a,b int)int { if a<b { return a } else { return b } }funcmax(a,b int)int { if a>b { return a } else { return b } }
这里 sort.Search 就是 Go 的标准库二分查找,巧妙避开手写指针的烦恼,边界条件也自然解决了。
总结:暖气器算法题,关键在于:
- Go 可以利用
sort.Search 和指针扫数组,高性能且简洁。
整个思路拿到手就像现场排查暖气器覆盖问题:房子、暖气器、半径,先把数组摆整齐,再扫一遍,边界全看清楚,就能跑满用例。