路灯覆盖所有房屋的最小半径
哪些公司问过
答案要点
- 问题转化:答案 = 所有房屋到最近路灯距离的最大值
- 朴素做法每个房屋枚举所有路灯,O(n·m)
- 优化:路灯排序后对每个房屋二分,比较左右两个候选路灯
- 二分法复杂度 O((n+m) log m);也可两数组排序后双指针
- 边界:房屋在所有路灯左侧或右侧时只有一个候选,注意越界与溢出
易错点
- 误以为答案是相邻路灯间距的一半
- 二分后只看右侧路灯,漏掉左侧更近的路灯
- 房屋在路灯范围外时下标越界
面试官常见追问
- 双指针怎么写?
- 如果要求最少放几个路灯覆盖所有房屋(半径固定)呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。