最小区间:k 个有序数组各取一数(LeetCode 632)
哪些公司问过
答案要点
- 转化:求最小区间,使 k 个数组各至少有一个元素落在区间内
- 小顶堆存每个数组当前元素,另用变量维护当前最大值
- 每轮用 [堆顶, 最大值] 更新答案,弹出堆顶并推入同数组的下一个元素
- 某个数组被取完即停止,此后无法让每个数组都有代表
- 复杂度 O(N log k),N 为元素总数,空间 O(k)
易错点
- 用大顶堆弹出最大值,方向搞反
- 某数组耗尽后继续循环
- 只维护堆,不单独记录当前最大值
面试官常见追问
- 为什么每次弹出最小值而不是最大值?
- 还有别的解法吗?
- 区间长度相同时如何取?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。