搜索二维矩阵一直是个挺能看出基本功的题面试里出现的频率不低。LeetCode 240题“搜索二维矩阵Ⅱ”比起第一版直接把矩阵从“每行首尾相接递增”升级成“每行从左到右递增、每列从上到下递增”整个解题思路就完全换了一套逻辑。很多人第一眼觉得这不就是个二维二分嘛结果一写就发现边界根本理不清越写越乱。这篇文章我从头到尾拆一遍把几种常见解法、复杂度推导、边界陷阱和调试经验一次说清楚希望能帮你把这道题彻底吃透。1. 题目到底在考什么先说清矩阵的规律1.1 矩阵的特殊性质这道题给的是一个 m x n 的矩阵满足两个条件每行从左到右递增每列从上到下递增。注意这里跟第一版“搜索二维矩阵”不一样第一版是每行递增且下一行第一个数大于上一行最后一个数整个矩阵拍平后就是一个严格递增的一维数组可以直接用一次二分。但这题没有“跨行连续递增”这个条件所以不能简单把二维数组展平后二分。我举个例子你就明白了[ [ 1, 4, 7, 11], [ 2, 5, 8, 12], [ 3, 6, 9, 16], [10, 13, 14, 17] ]这个矩阵里7的下方是88的下方是9但7的右边是1111明显大于8。也就是说整个矩阵并不是一个全局有序的序列而是行内有序、列内有序行与行之间只有局部单调性。这种“行列各自有序”的结构决定了你不能直接套一维二分的模板。但反过来它也给了你一个特别重要的线索右上角或左下角这个位置刚好是“行最大、列最小”的分界点从那里出发每一步都能排除一整行或一整列。1.2 哪些解法是“看似能用、实际坑人”很多人拿到这题的第一反应是既然矩阵行列有序那把每一行都做一次二分不就行了这个思路方向对但直接套模板会出问题。比如矩阵有 n 行每行二分需要 O(log m) 的时间整体复杂度就是 O(n log m)。如果 m 和 n 差不多这个复杂度能接受但如果你遇到的是一个 1x10000 的矩阵那就是 1 次二分没问题可如果遇到 10000x1 的矩阵那就是 10000 次二分每行只有一个元素二分变成 O(1)可还是得遍历 10000 行效率就很差。再比如有人想用“二维二分”也就是把矩阵切成四块每次排除一块。这个思路叫分治但切分之后剩下的区域不是矩形可能是 L 形递归的终止条件写起来很麻烦而且每次只能排除四分之一递归深度和常数都不小。不是不能做但面试时手写容易翻车。还有一个坑是“从左下角出发”。很多人知道右上角出发能排除行列就类比着从左下角出发。方向没问题但如果你搞混比较方向写出的条件判断就会反。我见过不少人在纸上推的时候是对的一写代码就用错了比较符号。2. 从右上角出发最优解为什么是 O(mn)2.1 核心思路右上角出发是我最推荐的解法也是这道题最经典的写法。核心逻辑就一句话把当前位置的值跟 target 比如果相等就返回 true如果当前值大于 target说明当前列的所有元素都大于 target因为这一列从上到下递增当前位置是最小的一个既然最小的都比 target 大那整列都可以丢掉所以向左移动一列如果当前值小于 target说明当前行的所有元素都小于 target因为这一行从左到右递增当前位置是最大的一个既然最大的都比 target 小那整行都可以丢掉所以向下移动一行。你可能会问为什么从右上角而不是左上角因为左上角是全局最小值向右向下都比它大你没法根据比较结果决定往哪走。右下角同理是全局最大值向左向上都比它小也没法决策。只有右上角行内最大、列内最小和左下角行内最小、列内最大这两个拐角位置才同时具备“向一个方向一定更大、向另一个方向一定更小”的性质。我打个比方你就懂了这就像在一个由高到低排列的山坡上找路你站在右上角往左走数字变小往下走数字变大每次比较后你都能确定一个方向是“死路”直接排除。整个搜索过程不会走回头路所以最多走 mn 步就能出结果。2.2 边界条件与终止条件写这道题最容易翻车的地方就是边界。我见过太多人 while 条件写错、越界判断漏掉、更新坐标的顺序搞反。这里我直接给你一个模板bool searchMatrix(vectorvectorint matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int rows matrix.size(); int cols matrix[0].size(); int row 0; int col cols - 1; // 从右上角开始 while (row rows col 0) { int current matrix[row][col]; if (current target) { return true; } else if (current target) { col--; // 排除当前列 } else { row; // 排除当前行 } } return false; }几个关键点我单独说明一下。首先是空矩阵的判断不能只判断 matrix.empty()还要判断 matrix[0].empty()否则你可能访问到不存在的元素。其次是循环条件只要 row 还在行数范围内、col 还在列数范围内就继续。第三是坐标更新比较结果是大于 target 就 col--小于 target 就 row方向别搞反了。2.3 为什么这个解法是线性复杂度这个解法的复杂度是 O(mn)不是 O(log(m*n))。怎么理解因为每次比较后要么 col 减一要么 row 加一循环里每执行一次必然会改变 row 或 col 的值一次。col 最多从 cols-1 减到 0row 最多从 0 加到 rows-1所以总的循环次数最多是 mn 次。这是个严格的数学上界不存在“最坏情况比这个更差”的可能。举例来说如果矩阵是 4 行 5 列最多比较 9 次。如果矩阵是 1000 行 1 列最多比较 1001 次其实就是从上到下走一遍。如果矩阵是 1 行 1000 列最多比较 1001 次相当于从左到右反着走一遍。这些极端情况在复杂度上都是线性级别不会退化。空间复杂度就更简单了只需要两个变量存坐标O(1) 的额外空间。3. 其他解法横向对比二分、暴力、分治3.1 逐行二分的写法与适用场景如果你就是想用二分也不是不行。逐行二分是“搜索二维矩阵Ⅱ”最朴素的正确解法思路简单对每一行做一次标准二分查找只要某一行找到了就返回 true全部行找完没找到就返回 false。def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False for row in matrix: left, right 0, len(row) - 1 while left right: mid (left right) // 2 if row[mid] target: return True elif row[mid] target: left mid 1 else: right mid - 1 return False这个写法复杂度是 O(m log n)。当矩阵特别“矮胖”比如只有两行、但每行有百万列时这个效率可以接受。但如果矩阵是正方形或者“瘦高”就不如右上角法了。我个人建议既然右上角法代码量差不多、思路也不难那优先掌握右上角法就好逐行二分作为一个备选思路理解即可。3.2 暴力遍历为什么不行最直接的想法肯定是一层一层遍历逐个比对时间复杂度 O(m*n)。你要说它错那确实没错但你要说它好那真谈不上。题目给了一个行列都有序的矩阵你要是还用全量遍历等于完全无视了题目给的条件面试官会觉得你没有利用已知信息优化算法的意识。我见过有候选人面试时说“暴力也能过”这话不算错尤其在小数据量、力扣普通测试用例下确实能跑完。但你想想如果矩阵是 10000 x 10000 呢一亿个元素暴力遍历在最坏情况下要做一亿次比较虽然现代计算机也不至于卡死但明显不是这道题想考察的“利用有序性”这个核心点。3.3 分治思想的引入与局限既然行和列都有序能不能用分治思路是这样的取矩阵中间值 matrix[midRow][midCol]如果 target 小于它那么右下角区域全部可以排除如果 target 大于它左上角区域可以排除。听起来很美好但问题是剩下的搜索区域不是规则矩形而是一个“L 形”或“反 L 形”递归时要同时处理两个子区域复杂度并不理想。严格分析的话这种做法的最坏时间复杂度是 O((mn) log(mn)) 甚至更差而且实现时需要注意的细节特别多。真在面试现场写非常容易在某一个 if 分支里漏掉一部分区域。我个人的建议是可以用分治思路跟面试官讨论展示你对递归和减治的理解但最终实现还是用右上角法最稳妥。4. 实操中的常见问题与调试心得4.1 我自己踩过的坑这题我写了不下十遍每次写都会遇到不同的坑这里直接把我踩过的都列出来给大家省点时间。第一个坑是 while 循环里坐标更新的方向搞反。由于矩阵的行是向下增长的所以“当前值小于 target”时应该 row也就是往下走但很多人惯性思维觉得“小于 target 应该往右走”写完就变成 col直接越界或者死循环。我建议你记这个口诀当前值太大就往左当前值太小就往下。第二个坑是取列数时用错了变量。矩阵的行数列数要分清行数是 matrix.size()列数是 matrix[0].size()。我见过有人把两者搞反结果在 4 行 5 列的矩阵里把初始 col 设成 4然后越界访问。写代码时建议命名清楚一些比如 rows 和 cols不要用 m 和 n 混着用。第三个坑是空矩阵判断。如果 matrix 是空数组matrix[0] 访问就会越界。但如果你只判断了 matrix[0].empty()遇到 matrix 本身为空时也会挂。所以判断顺序必须是先 matrix.empty() 再 matrix[0].empty()这里的顺序错误会导致未定义行为。第四个坑是性能相关的不要在一个循环里反复调用 matrix.size() 或 matrix[0].size()。虽然现代编译器可能帮你优化掉但养成用局部变量缓存尺寸的习惯是个好习惯尤其在嵌入式、算法竞赛等要求极高性能的场景。4.2 测试用例怎么设计写完之后怎么验证我的建议是按下面几个维度设计测试用例场景输入示例期望结果空矩阵[]false只有一行[[1,3,5,7]]分别测存在和不存在的值只有一列[[1],[2],[3]]分别测存在和不存在的值目标值在最左上角[[1,2],[3,4]]搜 1true目标值在最右下角[[1,2],[3,4]]搜 4true目标值不存在但介于某些值之间[[1,4],[2,5]]搜 3false全是相同值的矩阵[[1,1],[1,1]]搜 1true你可以发现单行单列是特别容易暴露初始化和循环条件错误的场景。很多人在 4x4 矩阵上跑得通一到 1x5 矩阵就翻车原因就是循环条件 col 0 和 row rows 在边界情况下容易被突破。4.3 关于“搜索入口”这类扩展问题很多人在刷完这道题之后会想到一个实际问题真实场景里有没有类似“行列有序”的搜索需求我简单提两个。一个是图像处理中的区域查询。如果你有一张按某种规则排序的特征图寻找某个像素值是否存在就可以借鉴这种从角落出发逐步缩小的思路。当然实际工程中图像不是简单递增的但这个“利用局部有序性剪枝”的思想是通用的。还有一个是数据库索引中的“Z 字形扫描”。在列存数据库里如果你知道某两列的数据分布满足某种偏序关系查找满足条件的记录时也能用类似从右上角出发的方式减少扫描范围。可以说这道题的本质就是“利用偏序关系做剪枝搜索”这个思想比代码本身重要得多。5. 我的一点个人体会这道题刷到后面我最大的感受是LeetCode 上的题不是让你背解法而是让你理解“信息量”这个东西。一个矩阵如果完全没有规律你要找到 target 只能全扫信息量是 O(m*n)但加上行列递增这个条件每个位置的数值就携带了“它右边都比它大、它下边都比它大”的信息右上角法就是把这些信息用到了极致每一步比较都在压缩剩余搜索空间。想明白这一点你就不会把这道题当成一个孤立的套路题而是能理解它背后的算法思想。如果你正在准备面试我建议你用这道题做“二分思想进阶”的敲门砖。先掌握右上角法再理解逐行二分最后看分治的局限三个层次下来你对“二维有序数据怎么搜”的理解就会上一个台阶。这比死记硬背一百道题都管用。