企业官网建设流程全解析

1. 这道题真正想考你的，不是“找元素”，而是“数个数”

LeetCode 378这道题，有序矩阵中第K小的元素，我第一次刷的时候差点被它骗了。题目给一个n乘n的矩阵，每一行从左到右升序，每一列从上到下升序，让你返回第K小的元素。看起来平平无奇，但真正动手写代码，你会发现很多“第一反应”的思路全都有性能隐患。这不是一道单纯考排序的题，它背后的核心考点是“计数”，更准确地说，是值域二分。

先说一遍题目要求，方便对不上的朋友直接进入状态。给定一个n x n矩阵，每行和每列都严格递增，整数K从1开始计数，要求返回矩阵中第K小的元素。比如矩阵是[[1, 5, 9], [10, 11, 13], [12, 13, 15]]，K=8，那答案就是13。这个13是矩阵排序后第八个数，不是第八行第八列，千万别搞混。

大多数人看到这题的第一反应是“无脑排序”。把矩阵里所有数丢进一个数组，排序，取第K-1个。这个思路没有任何算法层面上的错误，提交也能过，但它有两个问题：一是时间复杂度O(n^2 log n)，矩阵一旦到1000乘1000规模，也就是百万级数据量，排序的压力立刻上来；二是它完全浪费了题目给出的行递增、列递增这个关键条件。面试官把矩阵设计成有序，不是为了让你无视这个性质的，他是在等你用上这个性质。

那这道题真正舒服的解法是什么？答案是对值域做二分查找，每次猜一个中间值mid，然后统计矩阵中有多少个数小于等于mid，用这个数量和K比较，不断缩小区间，最后收敛到真正答案。你不需要直接锁定“第K小的元素是哪个”，你只需要不断缩小“答案所在的数值范围”，直到范围缩到不能再缩。这个过程非常像小时候玩“猜数字”游戏：对方心里想一个1到100的数，你每次报一个数，对方告诉你“大了”还是“小了”，通过log次数的猜测最终命中。矩阵里所有元素的最小值是左上角matrix[0][0]，最大值是右下角matrix[n-1][n-1]，第K小的元素一定在这个闭区间里，这就是值域二分成立的前提。

很多人会有个疑问：第K小的元素既然是矩阵中真实存在的数，我为什么不能在排序后直接定位？原因在于，值域二分不需要显式地把矩阵拍平，它只需要一个能快速统计“小于等于mid的元素个数”的方法，而这个方法恰好可以借助矩阵的行列有序性，做到O(n)而不是O(n^2)。这个统计方法，才是全题唯一真正需要动脑子的地方。

2. “猜数字”的核心引擎：从右上角出发的线性计数

2.1 为什么计数函数能做到O(n)

假设我们猜了一个数mid，现在要统计矩阵里有多少个元素小于等于它。最笨的方法是双层循环遍历整个矩阵，复杂度O(n^2)。但既然每行升序、每列升序，我们就可以利用这个“双重单调”的性质，把遍历压缩成一条路径。

我习惯从矩阵的右上角出发，也就是matrix[0][n-1]。这里有两个选择：如果当前元素大于mid，说明当前这一整列往下所有元素都大于mid，因为列是递增的，所以我们把列指针左移一格；如果当前元素小于等于mid，说明当前这一行从当前列往左的所有元素都小于等于mid，个数就是col + 1，累加到答案里，然后向下移动一行，去看看下一行有没有更多满足条件的数。

这个过程每一轮最多执行n次，最坏情况下就是从右上角一路走到左下角，总共2n步，复杂度是O(n)。这个“蛇形走位”的技巧，在这道题里就是核心中的核心。算法竞赛圈里这种做法有个常见的名字，叫双指针法，两个指针各自负责行和列，一个从左往右走，一个从上往下走，组合起来就是一条不超过2n的折线。

2.2 伪代码与一次完整推演

把上面的逻辑写成伪代码，大概是这个样子：

function countLessEqual(mid): row = 0 col = n - 1 ans = 0 while row < n and col >= 0: if matrix[row][col] <= mid: ans += col + 1 row += 1 else: col -= 1 return ans

这里ans += col + 1是关键。为什么是col + 1而不是col？因为列下标从0开始，如果当前元素在第3列，那这一行从第0列到第3列一共有4个元素满足条件，也就是col + 1。我没有写过for row in range(n)去逐行二分查找每一行的上界，那虽然时间复杂度也是O(n log n)，但实现上要复杂不少。直接从右上角出发的蛇形走位，是这道题最优雅的计数方式。

拿题目经典的例子推演一遍。矩阵[[1,5,9],[10,11,13],[12,13,15]]，假设mid=8。从右上角9开始，9大于8，左移列指针到5；5小于等于8，答案累加1 + 1 = 2，行指针到第1行；第1行第1列是11，大于8，左移到第0列，值为10，还是大于8，左移无路可走，行指针再往下到第2行，此时col已经小于0，循环结束，返回2。这表示小于等于8的数只有矩阵左上角的1和5两个，和肉眼判断结果一致。

2.3 二分框架怎么套

有了countLessEqual这个引擎，整个二分查找逻辑就非常朴素了：

• lo = matrix[0][0]，hi = matrix[n-1][n-1]
• 当lo < hi：
  • 取mid = lo + (hi - lo) / 2
  • 如果countLessEqual(mid) < K，说明第K小的数一定大于mid，令lo = mid + 1
  • 否则，说明第K小的数可能是mid，或者比mid更小，令hi = mid
• 最终返回lo

这个框架有一个和普通二分查找不太一样的地方：hi = mid而不是hi = mid - 1。原因是当countLessEqual(mid) >= K时，mid本身有可能是答案，如果直接hi = mid - 1，可能会把正确答案排除出搜索区间。这是整个二分“边界条件”里最容易写错的一环，先记下这个点，后面第三部分我会单独展开。

整体时间复杂度是O(n log(max - min))。n是矩阵边长，max-min是值域范围。矩阵1000乘1000时，值域范围就算到2的31次方，log也就是31左右，整体开销大约几万次操作，和排序法动辄百万级别的操作量比，差距非常明显。而且这个算法不依赖K的大小，K等于1还是等于n*n，时间复杂度完全一样，这也是它比堆方案稳健的原因。

3. 完整实现与代码逐行精讲

3.1 Java实现

public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int lo = matrix[0][0]; int hi = matrix[n - 1][n - 1]; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (countLessEqual(matrix, mid) < k) { lo = mid + 1; } else { hi = mid; } } return lo; } private int countLessEqual(int[][] matrix, int mid) { int n = matrix.length; int row = 0; int col = n - 1; int count = 0; while (row < n && col >= 0) { if (matrix[row][col] <= mid) { count += col + 1; row++; } else { col--; } } return count; }

3.2 Python实现

def kthSmallest(self, matrix: list[list[int]], k: int) -> int: n = len(matrix) lo, hi = matrix[0][0], matrix[-1][-1] while lo < hi: mid = (lo + hi) // 2 if self.count_less_equal(matrix, mid) < k: lo = mid + 1 else: hi = mid return lo def count_less_equal(self, matrix, mid): n = len(matrix) row, col = 0, n - 1 count = 0 while row < n and col >= 0: if matrix[row][col] <= mid: count += col + 1 row += 1 else: col -= 1 return count

3.3 每行代码背后的理由

先说lo = matrix[0][0]和hi = matrix[n-1][n-1]的取值。这两个值取自矩阵本身，保证答案一定在搜索区间内。有人会问，是不是可以把lo设置成整个矩阵的最小值，比如用Integer.MIN_VALUE？理论上可以，但没必要，而且从矩阵边界取值的做法还有一个额外好处：当矩阵只有一个元素时，lo和hi直接相等，循环一次都不会执行，直接返回这个元素，天然正确。

再来看lo + (hi - lo) / 2这个写法。很多初学者喜欢写(lo + hi) / 2，这在lo和hi都是正数且值域较大时，有整数溢出的隐患。Java里虽然矩阵值本身不会大到溢出int，但为了保证健壮性，写成lo + (hi - lo) / 2是习惯动作。这个写法本身不复杂，但能体现你对整数溢出风险的敏感度，面试时是个加分小细节。

计数函数里的count += col + 1，前面已经解释过为什么是col + 1。但还有一个隐藏细节需要注意：当matrix[row][col] <= mid时，我们只关心这一行从第0列到第col列的元素，然后row++；当matrix[row][col] > mid时，只做col--，并不移动行指针。这里有个容易绕晕的地方，为什么要按这个顺序更新？因为列指针左移后，当前行的新位置还是可能大于mid，所以需要继续左移，自然循环会在内部处理；行指针下移后，新行的当前位置则直接进入下一轮判断，把当前列的元素和mid再比一次。两个指针交错推进，直到一方越界，整个矩阵刚好被一条折线完整覆盖，不多算一个，也不少算一个。

提示：这个计数函数里没有用到任何排序库，也没有额外数组，只用了常数个变量，空间复杂度O(1)。在LeetCode 378的题解社区里，这个蛇形计数是最主流的做法，因为它在时间、空间、代码量三个维度上做到了最平衡。

4. 最容易翻车的三个边界问题，逐个拆给你看

4.1 当mid不是矩阵里的真实元素时，二分会不会失灵

值域二分有一个很反直觉的点：搜索过程中我们反复猜测的mid，很有可能根本不是矩阵里实际存在的数。比如矩阵[[1, 2], [3, 4]]，第一次mid = (1 + 4) / 2 = 2，2是真实元素，没问题；但如果值域继续缩小，比如lo = 1, hi = 2时，mid = 1，这里mid是真实元素；可如果是lo = 2, hi = 4，mid = 3，也是真实元素。你可能会觉得，这个例子里mid碰巧都是真实元素。可如果矩阵是[[1, 3, 5], [7, 9, 11]]，初始lo = 1, hi = 11，mid = 6，6就不在矩阵里。

那mid不是真实元素的时候，二分还能收敛到正确答案吗？能。因为二分查找的目标不是“命中mid恰好等于答案”，而是“找到最小的那个值x，使得countLessEqual(x) >= K”。当x不是矩阵元素时，countLessEqual(x)和countLessEqual(x - 1)的值完全一样，一旦发生这种“重复计数”，二分就会自然地继续把上界往下压，因为此时hi还是会等于一个更小的值，直到压到某个真实元素，计数发生跳变，这个真实元素就是答案。

换句话说，值域二分的本质是刻画了一个阶梯函数：横坐标是值域里的值，纵坐标是小于等于该值的元素个数。我们要找的，是纵坐标第一次大于等于K对应的横坐标，而这个横坐标必然落在矩阵实际元素的集合上，因为只有实际元素才会让计数发生跳变。你可以把“中间猜的那些非矩阵元素”理解为为了逼近跳变点而进行的试探，它们不会破坏结果。

4.2 当countLessEqual(mid)恰好等于K时，为什么不能直接返回mid

这是我在评论区见过最多的问题。很多初学者会写这样的逻辑：

if (countLessEqual(mid) == k) { return mid; }

这个写法在部分测试用例上是对的，但在有重复元素或mid不是矩阵元素时就会出错。举个具体例子。矩阵[[1, 2, 2], [2, 3, 3], [3, 4, 4]]，K=3。第一次lo=1，hi=4，mid=2。countLessEqual(2)统计出来是多少？矩阵里小于等于2的元素有第一行三个（1, 2, 2），第二行第一个也是2，一共4个。4大于等于3，所以答案可能是2，继续收缩上界到hi=2。此时lo=1，hi=2，mid=1，countLessEqual(1)只有1个，小于K，所以lo变成2。最后lo=hi=2，返回2，正确。

现在假设mid=3，countLessEqual(3)等于7，不是等于K，但mid也不是答案，答案仍然是2。再换一个场景，如果某个mid不是矩阵里的元素，比如mid=5，count可能恰好等于K，但你直接返回5，就等于返回了一个矩阵里根本不存在的数，直接WA。所以最稳妥的做法是：当countLessEqual(mid) >= K时，把hi压到mid，继续搜索，直到lo和hi重合。等搜索结束时，lo一定是一个真实存在于矩阵中的元素，而且刚好是第K小。这个收敛性证明依赖两点：矩阵元素集合是离散的，以及“最小满足count >= K的值”必然属于矩阵元素集合。理解了这个，你就知道为什么不能在中途提前return。

4.3 矩阵里大量重复元素时，返回值会不会有歧义

如果矩阵里有很多重复元素，比如上面例子里的2出现了三次，那第K小的元素可能有多个候选位置。值域二分遇到这种情况，依然能稳定返回正确的“数值”，也就是2。它不会区分“第3个2”和“第4个2”，因为题目要求返回的是元素值，不是元素下标。只要返回值是矩阵中真实存在的、且小于等于它的元素个数大于等于K，同时小于它的元素个数小于K，这个值就是唯一正确答案。即使矩阵里重复值很多，这个“数值”也是唯一的。

4.4 整数溢出问题的一个实际测试

我在本地用一个大矩阵做过测试。构造一个1000乘1000的矩阵，元素值接近int范围的上限，比如Integer.MAX_VALUE - 500000附近。如果用(lo + hi) / 2，在某些极端情况下中间值会超过int上限，变成负数，导致二分直接出错。改用lo + (hi - lo) / 2之后，这个问题彻底消失。虽然LeetCode的测试用例未必会这么极端，但在系统设计或面试白板题里，养成这个习惯总能规避一些莫名其妙的bug。

5. 值域二分之外的两种思路，以及它们的适用边界

5.1 思路一：把矩阵当成n个有序链表的归并

因为每一行都是升序的，矩阵天然可以看成n个有序链表。用一个小根堆，堆里先放每行的第一个元素，也就是每行的最小值。每次从堆里弹出当前最小的元素，计数加一，如果弹到第K个，直接返回。弹出一个元素后，把同一行的下一个元素入堆。这个思路的时间复杂度是O(K log n)，空间复杂度O(n)。

这个方案的优点是非常直观，几乎不需要动脑筋，按照“每次取全局最小”的思路一步步走，K次之后就是答案。而且它不需要利用列方向的有序性，只靠行有序就能工作。但它的问题是，当K接近n*n时，K log n会退化到O(n^2 log n)，和排序法不相上下，完全失去了“利用矩阵有序性”的意义。所以堆解法更适合“K非常小”的场景，比如K=1、K=2这类小题，或者面试官要求你现场给出一种“虽然不是最优，但能跑”的方案时。

5.2 思路二：直接排序

把矩阵所有元素放进一维数组，排序，返回第K-1个。代码量最少，但时间、空间都差。排序前需要O(n^2)的空间存数组，排序本身O(n^2 log n)。这个写法唯一的适用场景是快速提交通过用例、刷题初期找手感。真正到了面试环节，如果考官问“能不能优化”，你至少得会切换成值域二分。

5.3 三种思路的横向对比

从表格可以看到，值域二分在空间上是碾压级的优势，O(1)的额外空间意味着即便矩阵达到一亿个元素，你也不需要多分配任何内存。而堆归并虽然时间复杂度在K小时优于值域二分，但空间O(n)和代码复杂度让它不那么优雅。我在面试中实际被问过这道题，面试官明确表示，他期待听到的答案就是值域二分，因为这一题在LeetCode官方题解里也是以“二分搜索矩阵值域”为推荐解法的。

5.4 一个可以提速的小优化：提前终止计数

在countLessEqual函数里，如果中途发现count已经超过了K，其实可以直接返回，不用再继续遍历。因为这个值只用来和K比较，一旦超过K，结果恒为“大于等于K”。优化后代码可以改成：

private boolean enough(int[][] matrix, int mid, int k) { int n = matrix.length; int row = 0; int col = n - 1; int count = 0; while (row < n && col >= 0) { if (matrix[row][col] <= mid) { count += col + 1; if (count >= k) { return true; } row++; } else { col--; } } return false; }

这样一来，二分查找过程中，很多“明显mid太小”或“mid太大”的情况会在计数早期就结束，实际运行时间比不提前终止的版本要快不少。LeetCode的用例跑下来，大概能省掉10%左右的时间。这个优化的本质是“短路求值”，和逻辑运算里的&&、||是一个思路：结果确定后，就不再执行多余操作。如果你想让代码更紧凑，甚至可以把enough函数直接内联到二分循环里，不过为了可读性，我建议保留独立函数。

6. “第K小”在LeetCode里的两种变体与一种通用套路

6.1 变体一：LeetCode 875 爱吃香蕉的狒狒——最小速度的二分

先从这道题的题号说起，LeetCode 875，题名“爱吃香蕉的狒狒”。场景是：一堆香蕉，每堆数量不同，狒狒每小时只能吃一堆，速度是K根/小时，如果这堆不够K根就按整小时算。要求在H小时内吃完，求最小速度。很多人第一次见这道题，会本能地想用模拟或者贪心，但标准解法其实是“二分速度”。

为什么这题和378很像？因为它们的核心都是“值域二分 + 可行性验证”。378里，我们枚举mid去统计小于等于它的个数；875里，我们枚举速度mid去计算吃完所有香蕉所需的总小时数。如果总小时数小于等于H，说明速度可能太快了，能把答案缩小；否则说明速度太慢了，需要加码。这个“可行性验证函数”，就是875版本的countLessEqual。你在378里练会的enough函数写法，直接可以迁移过去。

6.2 变体二：LeetCode 994 腐烂的橘子——从“大小”二分到“步数”BFS

994这题从名字看和“第K小”完全不沾边，它给的是一个网格，里面有新鲜橘子和腐烂橘子，每分钟腐烂橘子会感染上下左右相邻的新鲜橘子，问网格里所有橘子都腐烂需要多少分钟，或者是否永远有橘子烂不了。这道题考的是多源BFS，每一分钟相当于BFS向外扩展一层，所以答案就是BFS的层数。

那它和378有什么关系？其实它们都在训练一件事：把抽象问题转化成数学问题的能力。378把“找第K小”转化成“有序矩阵值域上的计数问题”，994把“感染时间”转化成“图上多源最短路径的最大层数问题”。这两道题一横一纵，构成了LeetCode里两类常见的思维模型：一类是靠二分搜索逼近答案，另一类是靠状态扩散模拟演化。我建议你把375、994和378放在连续几天里做。做完这三道，你对“猜答案再验证”和“状态扩展”这两种套路都会形成肌肉记忆。

6.3 通用套路：看见这三个特征，先想值域二分

我在前面反复说“值域二分”，但很多读者可能还是停留在“这是一道题的一个解法”的层面。实际上，LeetCode里凡是带有以下三个特征的问题，都可以第一时间想到值域二分：

1. 存在一个可枚举的数值/速度/距离，且结果随该值单调变化
2. 题目要求的是一个满足条件的最小值或最大值
3. 能在给定该值的前提下，设计出一个O(n)或O(n log n)的可行性验证函数

第378题满足这三点中的每一条：数值是可枚举的值域，单调性是“小于等于mid的个数随mid单调递增”，验证函数是蛇形计数。第875题也满足：速度越大，吃完所需时间越短，验证函数是累加每堆所需时间。甚至很多看似和矩阵无关的题目，比如“分割数组的最大值”“在每个子树中找第K小”之类的，底层也都是同一个框架。

6.4 写在刷题路线里的心得

如果你在准备面试，我建议把378作为“二分答案”这一类题型的代表题反复刷三遍。第一遍直接看题解，理解值域二分的思路，用自己的语言把代码写出来；第二遍不看代码，盯着countLessEqual函数，尝试自己推导为什么从右上角出发能把计数做到O(n)；第三遍尝试把矩阵换成“每行升序但每列降序”的变体，思考蛇形计数需要怎么调整方向。这三遍走完，你对“有序数据结构的遍历方向”和“二分答案的循环不变量”都会有更深一层的理解。

我在实际刷题过程中还有一个体会：值域二分的代码一旦跑通，往往非常稳定，因为循环不变量清晰，边界条件固定。相比之下，堆解法需要担心堆的弹出顺序、入堆判重，排序法需要担心内存占用。如果你在面试现场写完值域二分后还有剩余时间，可以主动向面试官补充一句“这个解法的空间复杂度是O(1)，时间复杂度是O(n log(max-min))”，这会比单纯提交一个AC答案来得更亮眼。

LeetCode 378这道题，真正值得收藏的不是那几十行代码，而是背后“猜答案、验证、收敛、返回真实元素”这一整套思考链路。把这个链路吃透，你解决的不只是这一道Medium题，而是整个“第K小”家族的题目群。