题目重点：把乘积矩阵看作每行升序序列，堆合并取前 K，并解释正数、重复值与稳定平局前提。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入两个非降序正整数数组，返回 `(product,i,j)`，按乘积、i、j 排序；K≥0，K 超过总 pair 数时返回全部。题目只说 positive，若允许 0 仍单调但训练版拒绝以保持约束清晰。
- 同值不同索引视作不同 pair，不能按乘积去重。
解题路线
- 对 A 的每个 i，序列 A[i]×B[0], A[i]×B[1],… 因两数组正且 B 升序而非降；把每行首项放入 min heap。
- 每次弹出全局最小 (product,i,j) 并输出，然后把同行下一个 j+1 放回；始终每行只暴露最小未输出项，故堆顶为所有剩余 pair 的最小值。
- 只需初始化前 min(len(A),K) 行：第 i≥K 行的首项不可能在严格稳定按 (product,i,j) 的前 K 之外挤掉前 K 行各自首项；若实现不想证明，可初始化所有行，复杂度更直观。
- 负数会使每行乘积顺序反转，必须重新设计行方向/分组；不能将正数约束静默删除。
手动走一遍
A=[1,2]、B=[2,3,4]，乘积 pair 前四项按稳定索引规则为 (2,0,0)、(3,0,1)、(4,0,2)、(4,1,0)。两个乘积 4 均保留。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import heapq
def k_smallest_products(a: list[int], b: list[int], k: int) -> list[tuple[int, int, int]]:
"""Return (product, i, j), ordered by product then source indices."""
if k < 0 or any(x <= 0 for x in a + b):
raise ValueError("nonnegative k and positive values required")
if not a or not b or k == 0:
return []
if any(a[i] > a[i + 1] for i in range(len(a) - 1)) or any(b[j] > b[j + 1] for j in range(len(b) - 1)):
raise ValueError("sorted arrays required")
heap = [(a[i] * b[0], i, 0) for i in range(min(len(a), k))]
heapq.heapify(heap)
result = []
for _ in range(min(k, len(a) * len(b))):
product, i, j = heapq.heappop(heap)
result.append((product, i, j))
if j + 1 < len(b):
heapq.heappush(heap, (a[i] * b[j + 1], i, j + 1))
return result
复杂度
N=len(A)、M=len(B)、R=min(N,K)：建堆 O(R)，输出最多 K 项每项 O(log R)，总 O(R+K log R)，堆 O(R)、结果 O(K)。训练代码 20,000 组随机网格与全笛卡尔积排序 oracle 对照。
易错点与追问
容易失分的边界
- 把乘积相同的不同 pair 去重。
- 允许负数却仍假设每行升序。
- 只把 (0,0) 放堆，每次只右移/下移但无 visited，重复/漏 pair。
- K 大于 N×M 时越界。
- 把最小数对和最小乘积对混淆。
继续深挖
- 若数组允许零或负数？
- 只返回乘积不返回索引时重复如何定义？
- K 接近 N×M 时直接排序是否更简单？
- 数组在磁盘上时怎样批量顺序读？
