如何用堆找有序矩阵中的第 K 小元素？

简化版

如果矩阵每一行、每一列都有序，可以用小顶堆找第 K 小。

一种常见做法是先把每一行的第一个元素放入堆，每次弹出当前最小值，再把它所在行的下一个元素放入堆。弹出第 K 次时，就是第 K 小元素。

复杂度通常是 O(K log n)，其中 n 是行数。

详细版

把每一行看成一个有序链表，问题就变成「合并多个有序序列，并找到第 K 个」。

堆中保存三元组：

(value, row, col)

流程：

将每一行第 0 列放入小顶堆；
弹出堆顶，计数加 1；
如果该元素右边还有元素，就把右边元素入堆；
弹出第 K 次时返回。

维度	复杂度
堆大小	最多行数
时间	`O(K log rows)`
空间	`O(rows)`

这个方法适合 K 不太大时使用。

完整版教学

1. 题目为什么能转成多路归并

有序矩阵常见条件是：

每一行从左到右递增；
每一列从上到下递增。

堆解法主要利用「每一行有序」这个条件。

每一行都可以看成一个有序数组：

row0: 1,  5,  9
row1: 10, 11, 13
row2: 12, 13, 15

找整体第 K 小，就像合并 rows 个有序数组。

2. 堆里为什么只放每行当前候选

如果把所有元素都入堆，时间和空间都是 O(n^2) 级别，浪费了矩阵有序性。

更聪明的方式是：每一行只放当前还没被消费的最小元素。

当某行的元素被弹出后，该行的下一个元素才有资格成为候选。

小顶堆维护的是每一行当前指针指向的候选值，而不是整个矩阵。

3. 三元组为什么要带 row 和 col

堆顶弹出后，需要知道它来自哪一行、哪一列，才能把同一行的下一个元素加入堆。

因此堆元素通常是：

(matrix[row][col], row, col)

弹出 (value, r, c) 后，如果 c + 1 < cols，就加入：

(matrix[r][c + 1], r, c + 1)

这就是多路归并的标准套路。

4. 为什么弹出第 K 次就是答案

小顶堆每次弹出的是所有当前候选中的最小值。

由于每一行内部有序，一个元素右边的元素一定不小于它。只有当当前元素被弹出后，右边元素才可能参与全局竞争。

所以弹出序列就是整个矩阵元素按升序被逐步枚举的顺序。

第 K 次弹出的元素就是第 K 小。

5. 和二分答案法有什么区别

有序矩阵第 K 小还有一种常见解法：二分答案。

方法	时间复杂度	适合场景
堆	`O(K log rows)`	K 较小，容易实现
二分答案	`O(n log(valueRange))`	K 较大，矩阵方阵且值域可二分

堆法按顺序枚举前 K 个元素；二分法则不断猜一个值，统计小于等于它的元素数量。

6. 重复元素怎么处理

如果矩阵中有重复值，堆法不需要特殊去重。

题目问的是第 K 小元素，通常按元素个数计数，而不是按不同值计数。

例如：

1, 2, 2, 3

第 3 小是 2，不是 3。

7. 边界条件有哪些

实现时要注意：

边界	处理
K 为 1	返回全局最小值
行数小于 K	正常弹出 K 次
某行长度不同	入堆前检查该行非空
重复值	不去重
比较器	按 value 升序

如果是严格的 n x n 矩阵，代码会更简单；如果是多行不同长度数组，要额外判断每行长度。

8. 常见误区与追问

误区：必须把矩阵所有元素都放进堆。 只需要把每行当前候选放进堆，空间可以降到行数级别。
误区：重复值要去重。 第 K 小通常按元素出现次数计算，重复值不能去掉。
误区：堆法一定是最优。 当 K 很大时，二分答案可能更合适。
追问：为什么可以只向右扩展？ 因为把每一行看作有序序列，弹出某行当前元素后才加入同一行下一个元素。
追问：堆大小为什么最多是行数？ 每一行在堆里最多保留一个当前候选元素。

简化版

详细版