有序矩阵中第 K 小的元素

看一眼这个矩阵：这是我们的例子。每行从左往右变大，每列从上往下变大。最小值在左上角（1），最大值在右下角（15）。第 K 小一定落在这两者之间。

先想最直白的办法：最直白：把矩阵所有数塞进一个数组，排个序，第 K 个就是答案。简单，但完全没用上「行列已经有序」这个宝贵条件。

为什么不够好：矩阵本来就半有序了，全摊开重排等于把现成的顺序信息扔掉重做。我们想要一个能吃下有序性的更快办法。

关键反转：反转思路：不去找第 K 小「在哪个格子」，而是在数值上二分。问自己：值 x 能不能当第 K 小？关键工具是「数出矩阵里 ≤ x 的有多少个」。

二分为什么成立：把值域 [最小, 最大] 当作搜索区间。x 越大，count(≤x) 越大，这是单调的。我们要找最小的 x，使得 count(≤x) ≥ K——这个 x 必然是矩阵里真实存在的第 K 小。

怎么数 ≤ x 才快：数 ≤ x 不用挨个看。站在左下角：如果当前格 ≤ x，那它头顶这一整列（含自己）都 ≤ x，一次加一列、再往右走；如果当前格 > x，就往上缩。走一条阶梯线，只需 O(n) 步。

二分开局 · 定值域：值域下界 = 左上角最小值 1，上界 = 右下角最大值 15。我们在 [1,15] 这个数值区间上二分，而不是在格子位置上。

第 1 轮 · mid=8 · 从左下角起步：取 mid = (1+15)/2 = 8。开始数矩阵里 ≤ 8 的个数：指针落在左下角 (2,0)，那里的值是 12。

第 1 轮 · 12 > 8 → 上移：当前格 12 大于 8。因为列是往下递增的，它下面只会更大，所以这一格不算、整列下半截都排除，指针上移到 (1,0)=10。

第 1 轮 · 10 > 8 → 再上移：10 还是 大于 8，继续上移到 (0,0)=1。注意我们一路只往上，从没回头——这就是阶梯走法只要 O(n) 步的原因。

第 1 轮 · 1 ≤ 8 → 整列计数 + 右移：1 ≤ 8！当前在第 0 行，所以从顶到这里只有 1 个格子 ≤8，count += 1。这一列处理完，指针右移到 (0,1)=5。

第 1 轮 · 5 ≤ 8 → 再 +1 右移：5 ≤ 8，又是第 0 行，count 加到 2。右移到 (0,2)=9。

第 1 轮 · 9 > 8 → 上移出界，统计完：9 大于 8，上移就越出了矩阵顶部，阶梯走完。count(≤8) = 2，远小于 8，说明第 8 小的值比 8 大。

第 1 轮判定 · 收窄到右半：count 还不够 8，说明 mid=8 偏小，第 8 小一定 ＞8。把下界抬到 lo = 8+1 = 9，值域收窄成 [9,15]。二分区间砍掉一半。

第 2 轮 · mid=12 · 左下角起步：新区间取 mid = (9+15)/2 = 12。再从左下角 (2,0) 起走一遍阶梯，当前值是 12。

第 2 轮 · 12 ≤ 12 → 整列 +3 右移：(2,0)=12 ≤ 12，它在第 2 行（最底行），头顶整列 3 个都 ≤12，count += 3。右移到 (2,1)=13。

第 2 轮 · 13 > 12 → 上移：(2,1)=13 大于 12，上移到 (1,1)=11。注意指针只往上、不回头。

第 2 轮 · 11 ≤ 12 → +2 右移：(1,1)=11 ≤ 12，它在第 1 行，从顶到这里有 2 个格子 ≤12，count 加到 5。右移到 (1,2)=13。

第 2 轮 · 13 > 12 → 上移：(1,2)=13 又 大于 12，上移到 (0,2)=9。

第 2 轮 · 9 ≤ 12 → +1 统计完：(0,2)=9 ≤ 12，第 0 行只 +1，右移就越出矩阵右边界，阶梯走完。count(≤12) = 6。

第 2 轮判定 · 仍偏小：count(≤12) = 6，还不到 8，第 8 小仍然比 12 大。下界抬到 lo = 13，区间收成 [13,15]。越来越逼近答案了。

第 3 轮 · mid=14 · 阶梯统计：mid = (13+15)/2 = 14。阶梯统计：(2,0)=12 那列贡献 3 个、(2,1)=13 贡献 3 个、(2,2)=15>14 上移、(1,2)=13 贡献 2 个，合计 count(≤14) = 8。

第 3 轮判定 · 收窄到左半：count(≤14) = 8 ≥ 8 达标了！但 14 不一定是答案——可能有更小的值也满足。所以是 hi = mid = 14（保留 14，不减 1），继续往小处试。区间变 [13,14]。

第 4 轮 · mid=13 · 再统计一遍：mid = (13+14)/2 = 13。再走阶梯：12 那列 +3、13 那列 +3、15>13 上移、(1,2)=13 +2，合计还是 count(≤13) = 8。13 也满足！

第 4 轮判定 · 区间锁定：count(≤13) = 8 仍 ≥ 8，于是 hi = 13。此刻 lo 和 hi 都等于 13，区间收成一个点，二分收敛，答案锁定。

答案 · 第 8 小 = 13：收敛到的 13 就是第 8 小。它必然是矩阵里真实存在的数：因为 count(≤13)=8≥8 且 count(≤12)=6没有真的去排序。

为什么收敛值一定在矩阵里：如果 x 不在矩阵里，那 count(≤x) 和 count(≤x-1) 会相等，x-1 也满足，x 就不会是「最小」的。所以二分停下来的值必然是矩阵里真实存在的数——这正是「二分答案」的精髓。

提速对比：每轮二分用 O(n) 阶梯统计一次，二分轮数是 log(最大值−最小值)。相比全摊开排序，又快又省空间（额外只用常数空间）。

本质金句：「二分答案」是个大套路：当答案具有单调判定性质（值越大越容易满足），就别去枚举位置，直接在数值范围上二分，配一个 O(n) 的计数器去判定。

易错实演 · hi 写成 mid-1 会跨过：想象答案恰好就是当前 mid（红色这两个 13）。如果 count≥k 时贪图收快写成 hi=mid-1，就把可能是答案的 mid 排除了，区间会越过真值导致结果偏小。务必 hi=mid。

边界三连：k=1 收敛到最小值、k=n² 收敛到最大值、1×1 直接返回——值域二分的边界都被 while(lo<hi) 自然兜住，不用特判。

面试追问：面试常追问「阶梯统计为什么 O(n)」和「为什么答案一定在矩阵里」，把这两点讲透，能体现你对单调性与二分答案的真正理解。