搜索二维矩阵 II：从双指针到 Z 字形搜索的算法精讲

老读者应该知道我每隔几天就会写一篇“每天学习一点算法”的笔记今天这篇主角是搜索二维矩阵 II。这个题目在力扣上是第 240 题属于“白板编程”面试里的高频题型表面看是套了一个二维数组的壳实际考的是有序数据结构的观察能力和双指针思路。你不用被“二维矩阵”四个字吓到拆开了讲它比很多人想象中要简单但简单背后又藏着一个很容易想歪的坎值得花十几分钟好好捋一遍。这道题解决的实际问题是在一个行方向递增、列方向也递增的矩阵里快速定位目标值。适用人群是刚开始刷题的大一学生、准备校招和跳槽的研发岗候选人以及想补一补算法基础的朋友。今天这篇文章会把这个题从暴力解法一路推导到最优解法把每一步的“为什么”讲清楚最后再附上我实际调试中踩过的坑和变式题的延伸思路。1. 题目到底在问什么读懂题面别在一开始就踩坑1.1 题面拆解行升序 列升序意味着什么题目给的是一个m x n矩阵目标值记作target。关键约束只有一句话每行的元素从左到右升序排列每列的元素从上到下升序排列。注意这个条件和“每一行都是整体有序的一维数组”有本质区别我见过不少人在这一步就开始跑偏。举一个具体的 4x4 矩阵例子1 4 7 11 2 5 8 12 3 6 9 16 10 13 14 17这个矩阵里第一行是[1, 4, 7, 11]严格递增第二行是[2, 5, 8, 12]严格递增每一列比如第一列[1, 2, 3, 10]也是严格递增。但是行与行之间并没有保持“首尾相接”的全同顺序第二行的元素并不都大于第一行的所有元素比如第二行第一个元素 2 就小于第一行第四个元素 11。所以矩阵整体呈现的是一个“比一维有序更弱、比完全无序更强”的偏序结构。正是这种特殊的偏序决定了不能用最简单粗暴的全局二分一气呵成也决定了后面要讲的右上角出发法能跑出那么漂亮的线性复杂度。1.2 容易随手写出的暴力解法复杂度是多少拿到题后最直接的想法肯定是双重循环把所有格子扫一遍。这个写法不能说错但明显没有利用题目条件时间复杂度是 O(m×n)在矩阵规模大时会非常吃力。比如一个 1000×1000 的矩阵最坏情况要遍历 100 万个格子。还有一个更容易被忽略的细节暴力解法的代码虽然简单但如果矩阵不是正方形也就是 m 和 n 不相等双重循环的边界条件写错同样会越界。这里给个小技巧建议先取行数m len(matrix)再取列数n len(matrix[0])只要第一行或第一列为空直接返回 false。这一步称之为“防御性校验”在真实面试中能避免不少尴尬。不过既然是算法题暴力肯定不是终点。题目真正想考察的是你能否利用行列递增的约束把时间从 O(m×n) 降下去。2. 三大主流解法横向对比暴力、二分、Z字形2.1 暴力遍历能过但不推荐暴力解法的代码非常短面试时如果你第一时间写出来也能算一个保底方案。但这里有一个心理博弈的细节如果想在面试中展示自己的算法功底暴力解法只能在你说不清更优思路时作为兜底而不是作为最终答案交付。因为面试官下一个问题几乎一定是“能不能降一下复杂度”从实际刷题角度暴力解的定位是用来和优化解法对拍的。我自己在本地调最优解时就会先写一个暴力版本生成随机矩阵和目标值然后对比两种写法输出是否一致。这个习惯在算法题调试里很实用尤其是像这种带有搜索性质的题对拍能帮你快速锁定逻辑错误而不是对着样例数据干瞪眼。2.2 逐行二分有优化但还不够彻底比暴力稍微进阶一点的做法是对每一行单独做一次二分查找。因为每一行内部是严格升序的所以对每一行调用标准的二分模板整体时间复杂度是 O(m × log n)。这个写法在思路上完全不复杂就是把一维二分搬进循环。可它的瓶颈也很明显依然是线性级别的外层扫描没有充分利用列方向也有序这个信息。换句话说逐行二分的视角还停留在“一行一行独立看”没有把整个矩阵当成一个整体来考虑。还有一种更进阶的写法是“对角线二分 分块排除”能把复杂度压到 O(log m log n) 甚至更优但对边界条件要求特别高面试场合反而不容易写对性价比不高。真正高频、好写、好讲清楚的解法是下面要展开的 Z 字形搜索。2.3 Z字形搜索为何是这个题的标准答案Z 字形搜索也叫阶梯搜索、线性搜索、右上角出发法它的核心思想只有一句话从右上角开始把矩阵看成一颗以右上角为根、向左和下两个方向生长的决策树。为什么说它是这个题的标准答案因为在所有能利用行列双递增条件的写法中它的代码最短、最难写错、复杂度 O(mn) 又足够优秀而且每一步移动方向是唯一确定的。对于面试场景来说“能快速写对”常常比“理论上最快”更重要。你可以在回答里点一句这个问题本质上是“有序矩阵中搜索目标”的模板题掌握右上角出发的写法之后很多类似题目都能套用。我当年第一次做这道题时也纠结过“为什么不从左上角出发”。左上角是整个矩阵的最小值从它开始向右和向下都比它大两个方向都可能是目标所在方向这就没法唯一决策走了第一步之后还得回溯。从右上角出发当前格子的左边一定更小、下边一定更大比较一次就能排除一行或一列。左下角其实也可以对称地看从左下角出发上边更小、右边更大一样成立。3. Z字形搜索的每一步从右上角出发的完整推演3.1 为什么是右上角而不是左上角这一步是理解整套解法的关键值得单独展开。看下面的矩阵1 4 7 2 5 8 3 6 9假设目标值是 6。从右上角的 7 开始看7 和 6 比较7 比目标值大。由于每一列从上到下是递增的而当前元素已经是这一列的最顶格那这一列剩余的元素往下只会越来越大绝对不可能出现 6所以整列都可以排除。接着再看左边的 44 比 6 小。因为每一行从左到右递增而当前元素已经是这一行的最右端这一行剩余元素往左只会更小也不可能出现 6所以整行都可以排除。于是每次比较结束要么找到了目标要么排除一行要么排除一列。这种做法的本质是用右上角这个“行最大、列最小”的特殊位置让比较结果永远只有一个排除方向。换成左上角因为它是行最小也是列最小如果当前值比目标小向右和向下都有可能是目标决策就分叉了递归下去会变成搜索一棵二叉树复杂度退化到指数级。3.2 完整代码实现与边界处理写代码前先想清楚三个变量row表示当前行初始 0col表示当前列初始 n-1循环继续的条件是 row 不越下界、col 不越左界。用 Python 写出来是这样def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) row, col 0, n - 1 while row m and col 0: if matrix[row][col] target: return True elif matrix[row][col] target: col - 1 else: row 1 return FalseC 版本大同小异class Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int m matrix.size(), n matrix[0].size(); int row 0, col n - 1; while (row m col 0) { if (matrix[row][col] target) { return true; } else if (matrix[row][col] target) { --col; } else { row; } } return false; } };这里有几个边界处理细节需要重点记住。第一个是矩阵可能为空即matrix []或者matrix[0] []这两种情况都有可能出现如果一上来就取matrix[0]会直接抛异常。第二个是 while 条件必须是row m col 0不能写成row m col 0因为当 row 走到 m 时矩阵已经越界此时没有必要再访问matrix[row][col]。第三个细节当matrix[row][col] target时当前列整列剔除不只是当前元素剔除所以用col - 1而不是原地继续向上这一点最容易在初学阶段绕进去。3.3 复杂度推导与过程收敛性分析为什么这个算法最坏情况是 O(mn) 而不是 O(m×n) 或者指数级关键在于每一步的操作只能二选一要么行号加一要么列号减一。行号从 0 最多加到 m-1列号从 n-1 最多减到 0两个变化方向都是单调的不存在“走过去又走回来”的情况所以总步数上界就是 mn。我见过一个很直观的类比把右上角出发的路径想象成一条楼梯。你从房顶一直往楼下走每一步要么往左一步要么往下一步永远不可能回头往上爬。楼梯总共的台阶数就是行数和列数的总和所以最多走 mn 级台阶就一定会到达楼梯的尽头。这个解释放到面试里会比单纯报复杂度数字生动很多。有一点值得补充如果矩阵是 1×n 或者 m×1 的退化情况这个算法同样适用本质上就退化成一行或一列上的线性扫描。这是它比某些依赖对角线性质的写法更健壮的原因之一。4. 常见错误与排查技巧实录4.1 边界条件写错导致越界或死循环这个题报错的典型方式有三种数组越界、死循环、答案错但看不出逻辑问题。数组越界多半发生在 while 条件写反了顺序比如写成while (col 0 row m)而没注意 row 和 col 的更新逻辑或者循环体里先访问matrix[row][col]再更新指针结果访问了一个不存在的格子。死循环几乎没有因为变量单调变化但我见过有人把row 1写成row row 1以外的问题在比较结果相等的情况下忘了 return。此时程序会继续走循环但 row 和 col 不再变化直接卡死。如果你用 Java 或 C 调这道题这个低级错误非常容易出现因为 IDE 不会给你任何警告只有跑用例时表现异常。我的排查建议是把矩阵换成 1×1 的最小用例比如matrix [[5]]目标值分别试 5、4、6 三个用例确定等值、偏大、偏小三条分支都正常再去测大矩阵。4.2 把“行升序列升序”误当成“整体可二分”这是我见过最多人掉的坑。本质上题目给的矩阵并不是一个能拉直成一维有序数组的结构比如前面举的1 4 7 11 2 5 8 12拉直后是1, 4, 7, 11, 2, 5, 8, 12这显然不是单调的所以不能直接对整个矩阵跑全局二分。也有一部分人想到“先用外层二分锁定行再在内层二分锁定列”这也不成立因为锁定行的时候需要知道目标值在哪两行之间但行之间的首尾大小关系不是完全有序的。哪怕matrix[i][0]按列递增也不代表第 i 行的最大值一定小于第 i1 行的最小值。这个问题在面试现场经常作为追问出现。面试官会故意问你“既然行列都有序能不能二分”你要能清楚地回答不能并给出一个反例比如两行两列的矩阵[[1, 4], [2, 5]]拉直之后就不是有序的。能讲清楚这个反例比背十遍代码都管用。4.3 时间复杂度估算错误还有一部分读者写对了代码但分析复杂度时说错。要注意Z 字形搜索并不是每次都能保证排除一整行或一整列最坏情况下它排除的总行数和总列数加起来是 mn中间有些步骤是排除行有些是排除列。所以正确说法是 O(mn)不能简单说 O(m) 或 O(n)。如果被追问“这和二分查找比哪个快”要分场景回答如果 m 和 n 数量级相差很大逐行二分的 O(m log n) 可能在 m 很小的时候比 O(mn) 还快。比如矩阵是 2 行 1 亿列逐行二分大概只需 2×27 次比较而 Z 字形最多要走 1 亿步。但从算法题的平均场景和代码简洁度来看Z 字形仍然更通用、更好写。在实际工程里如果矩阵是行多列少也可以选左下角出发本质是对称的步数上界仍是 mn。5. 变式题与复盘一个解法吃透一类题5.1 和“搜索二维矩阵 I”的区别力扣上还有一道题叫“搜索二维矩阵”题号 74它和今天这一题长得非常像但条件多了一条上一行的最后一个元素小于下一行的第一个元素。这个额外条件让整个矩阵可以拉直成一个严格递增的一维数组所以直接对整个一维数组做二分即可。你甚至可以不用真去拉平数组只需要把一维下标映射为矩阵行列下标def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid (left right) // 2 mid_val matrix[mid // n][mid % n] if mid_val target: return True elif mid_val target: left mid 1 else: right mid - 1 return False写这道题时最容易错的映射关系是matrix[mid // n][mid % n]。有人会写成mid // m或mid % m在 m 不等于 n 时就直接算错了。这道题恰好可以作为“搜索二维矩阵 II”的对照题一个是二维结构里有额外强约束一个是仅行列局部有序。放在一起复习对矩阵类二分的理解会深很多。5.2 同一思想的其它变式Z 字形搜索的核心思想——选择一个“角点”作为起点让每一步决策方向唯一化——还能延伸到不少题目。比如力扣 1351“统计有序矩阵中的负数”同样可以利用右上角出发如果当前元素为负数则说明这一列下面的元素都为负数可以直接统计并移动列指针复杂度也能压到 O(mn)。再比如剑指 Offer 04“二维数组中的查找”其实就是力扣 240 的翻译版解题思路完全一致。还有一个常见的场景是有序矩阵中的第 K 小元素力扣 378。那道题更复杂需要结合二分答案和计数查找跟今天的主题不完全一样但基础依然是“利用行列有序来判断矩阵中不超过目标值的数量”。如果你今天能把 Z 字形搜索彻底吃透再做 378 会轻松不少因为计数过程本质上就是沿着类似阶梯的路径扫描。所以我的建议是不要只刷完 240 就完事而是把它当成一个“锚点题”把相同思想、相同数据结构的题串起来复习。算法能力的提升从来不是靠题量堆积而是靠这种模式归并和对比复盘。6. 小结后的两个实用建议其实这类搜索类题目的通法可以总结成一句话当数据有某种单调性时优先考虑能不能用双指针或二分把搜索空间快速收缩。搜索二维矩阵 II 考察的并不只是记忆一个特定解法而是你有没有能力识别出“行有序、列有序”这个线索并选择合适的切入点。另外给刷题的新手一个建议拿到这类题先花一分钟在纸上把矩阵画出来用眼睛模拟一遍从右上角出发的路径再写代码。我自己的经验是直接在编辑器里敲代码很容易跳过关键观察但把路径画出来之后边界条件和循环不变式会自然变得清晰。不要觉得画图浪费时间算法题最耗时的从来不是打字而是想明白。希望这篇“每天学习一点算法”的复盘对你有帮助。如果你也在刷这道题欢迎试试从左上角出发然后被迫回溯的痛苦再回来体会右上角这一个角的选择为什么这么巧妙。