题目描述
思路解析动画文字版
记住这条「行首入堆·弹最小·只补右邻一对」，下面每一步都在套它。
开始：堆是空的（容量 3）。先把 nums1 每个数配 nums2[0]=2 的对依次入堆——它们是每一行里和最小的候选。
把 (1,2) 入堆： 先放到堆末尾(下标0)，再按对和向上浮到该去的位置。
把 (7,2) 入堆： 先放到堆末尾(下标1)，再按对和向上浮到该去的位置。
新对 (7,2)和9 ≥ 父 (1,2)和3，停止上浮、就位(绿)。堆顶 (1,2)仍是当前最小和。
把 (11,2) 入堆： 先放到堆末尾(下标2)，再按对和向上浮到该去的位置。
新对 (11,2)和13 ≥ 父 (1,2)和3，停止上浮、就位(绿)。堆顶 (1,2)仍是当前最小和。
堆顶 (1,2) 和=3，是当前所有候选里对和最小的，弹出收进答案。
(1,2) 收进答案(第1对)。把堆末元素 (11,2) 暂放堆顶(紫)，再按对和向下沉。
比较 (11,2)和13 与较小子 (7,2)和9：子更小，下沉交换。
交换完成，(11,2)沉到下标1。
(11,2) 对和已不大于子节点，下沉结束(绿就位)，堆顶 (7,2)又是当前最小和。
刚弹的对来自 nums1[0]=1 这行，补它右邻 (1,4) 入堆： 先放到堆末尾(下标2)，再按对和向上浮到该去的位置。
比较新对 (1,4)和5 与父 (7,2)和9：更小，上浮交换。
交换完成，新对上浮到下标0。
新对 (1,4)和5 已浮到堆顶，就是当前最小和，就位(绿)。
堆顶 (1,4) 和=5，是当前所有候选里对和最小的，弹出收进答案。
(1,4) 收进答案(第2对)。把堆末元素 (7,2) 暂放堆顶(紫)，再按对和向下沉。
(7,2) 对和已不大于子节点，下沉结束(绿就位)，堆顶 (7,2)又是当前最小和。
刚弹的对来自 nums1[0]=1 这行，补它右邻 (1,6) 入堆： 先放到堆末尾(下标2)，再按对和向上浮到该去的位置。
比较新对 (1,6)和7 与父 (7,2)和9：更小，上浮交换。
交换完成，新对上浮到下标0。
新对 (1,6)和7 已浮到堆顶，就是当前最小和，就位(绿)。
堆顶 (1,6) 和=7，是当前所有候选里对和最小的，弹出收进答案。
(1,6) 收进答案(第3对)。把堆末元素 (7,2) 暂放堆顶(紫)，再按对和向下沉。
(7,2) 对和已不大于子节点，下沉结束(绿就位)，堆顶 (7,2)又是当前最小和。
已弹满 3 对，按和从小到大依次是 (1,2)、(1,4)、(1,6)，正是答案。
空数组、k 超过总对数、单元素三个边界先想清。
两个高频追问：初始只入 min(k,m) 个、元素为何带下标。
参考代码
import heapqdef kSmallestPairs(nums1, nums2, k): if not nums1 or not nums2: return [] h = [] # 最小堆: (对和, i, j) for i in range(min(k, len(nums1))): heapq.heappush(h, (nums1[i]+nums2[0], i, 0)) res = [] while h and len(res) < k: _, i, j = heapq.heappop(h) # 弹最小对 res.append([nums1[i], nums2[j]]) if j + 1 < len(nums2): # 只补右邻一对 heapq.heappush(h, (nums1[i]+nums2[j+1], i, j+1)) return res复杂度
- 时间：O(k log k)，初始入堆 min(k,m) 个，之后每弹一对补一对、各 O(log k)，共弹 k 次
- 空间：O(min(k, m))，堆里最多 min(k, m) 个候选（每行至多一个）
易错点
面试追问把动画讲成自己的话
追问初始为什么入堆只放 min(k, m) 个，而不是全部 m 个行首？
追问为什么堆元素要带上 i、j 下标？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分割数组为连续子序列
LeetCode 659 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题