LeetCode 74题“搜索二维矩阵”经常有人在刷 Hot 100 的时候卡住。其实这道题属于典型的“题目唬人、解法直白”一看到二维矩阵很多人下意识就想 BFS、DFS 或者动态规划反而把简单问题复杂化。我前两天重新用三种思路各写了一遍把边界条件盘了一轮今天把这题从题意到变体彻底讲透。先说结论这道题在 hot100 里的最优解并不是“二维搜索”而是把矩阵当成一维有序数组做二分。原因在于题目给了两个非常强的约束——每行从左到右递增并且上一行的末尾严格小于下一行的开头。这两个条件合在一起意味着整个矩阵按行展开后就是一个严格递增的序列。抓住这一点代码可以短到不可思议时间复杂度直接压到 O(log(m*n))。这篇文章会从题意拆解、三种解法、边界踩坑、240题变体一直聊到 hot100 的刷题站位。不管你是一刷还是三刷都值得花十分钟把细节过一遍。1. 先看懂题意全局有序四个字才是题眼1.1 题目到底在说什么输入是一个 m x n 的整数矩阵 matrix 和一个目标整数 target要求判断 target 是否存在于矩阵中存在返回 true否则返回 false。矩阵满足两个条件每行中的整数从左到右按升序排列每行的第一个整数大于前一行的最后一个整数。第二个条件很容易被忽略但它才是这道题的命门。比如标准示例里的矩阵[[1,3,5,7], [10,11,16,20], [23,30,34,60]]第一行末尾是 7第二行开头是 10第三行开头是 23行与行之间是“无缝衔接”的递增关系。这和其他矩阵题很不一样很多矩阵只保证“每行递增、每列递增”但行与行之间没有这种全局衔接关系。后者是 240 题的情况解法完全不同后面我会专门对比。1.2 两条约束合并后的隐藏结论设矩阵第 i 行第 j 列的元素为 a[i][j]行数为 m列数为 n。由条件一可知行内严格递增a[i][0] a[i][1] ... a[i][n-1]由条件二可知行间严格衔接a[i][n-1] a[i1][0]把两条串联起来整个矩阵按“第一行、第二行、第三行……”的顺序展开后a[0][0] a[0][1] ... a[0][n-1] a[1][0] ... a[m-1][n-1]这是一个完全有序的序列。换句话说这题本质上就是一个“有序数组里找 target”的问题只不过数组的元素被二维矩阵包装了一下。看到有序序列第一反应就应该是二分查找而不是 DFS。1.3 空矩阵与输入边界题目通常给的 m、n 都是正整数但 LeetCode 的测试用例经常会有空二维数组比如[]或者[[]]。写代码时如果不做判空matrix[0]会直接越界报错。所以无论用哪种解法开头第一件事都是if not matrix or not matrix[0]: return False先判断 matrix 本身是否为空再判断第一行是否存在顺序不能反。这一行代码能帮你避开一半以上的低级报错。2. 最优解一维映射二分把矩阵拉直2.1 下标换算电影票和座位的对应关系要把二维矩阵当成一维数组来二分关键就是下标换算。假设矩阵有 m 行 n 列我们用一维下标 k 表示第 k 个元素那么 k 和二维坐标 (row, col) 的对应关系是row k // n col k % n注意这里除的是列数 n不是行数 m。这个公式可以类比电影院的座位编号一张票上写着“第几排第几座”但系统里存的可能只是一个连续的座位号你拿到座位号后要反过来算出自己在哪一排。这里的row k // n就是在算“第几排”col k % n就是在算“第几座”。为什么除的是 n因为一维下标 k 是从 0 开始每走 n 个元素就换一行。比如一个 3 行 4 列的矩阵总共 12 个元素下标 5 对应的是5 // 4 1行、5 % 4 1列也就是第 1 行第 1 列的元素。如果错写成k // m在 m ! n 的时候就会取到完全不同的位置。2.2 完整代码与逐行拆解Python 版本也是我觉得最清晰的一版def searchMatrix(matrix, target): # 先判空不然 matrix[0] 会越界 m len(matrix) if m 0: return False n len(matrix[0]) if n 0: return False left, right 0, m * n - 1 while left right: mid left (right - left) // 2 row mid // n # 第几行 col mid % n # 第几列 value matrix[row][col] if value target: return True if value target: left mid 1 else: right mid - 1 return False逐行逻辑其实很简单。left和right是“虚拟一维数组”的左右端点初始时覆盖整个矩阵每次取中点mid通过mid // n和mid % n还原成真实坐标拿到的中间值和 target 比较后按照标准二分的规则收缩区间。循环结束还没找到说明 target 不在矩阵里。C 版本也放一份方便面试手写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 left 0, right m * n - 1; while (left right) { int mid left (right - left) / 2; int val matrix[mid / n][mid % n]; if (val target) return true; else if (val target) left mid 1; else right mid - 1; } return false; } };C 里我特意写成left (right - left) / 2而不是(left right) / 2是为了避免 left 和 right 都很接近整数上限时相加溢出。Python 没有这个问题但养成这个习惯没坏处。2.3 正确性由“区间不变量”保证二分查找最容易让人心虚的地方是“我到底会不会漏掉答案”。要消除这种心虚靠的是区间不变量[left, right]始终是一个闭区间它里面装着所有“ target 可能存在的下标”。每次比较中间值后要么直接命中要么因为整个序列有序target 只可能落在左半边或右半边于是把区间收缩一半。当left right时区间为空说明 target 确实不存在。这个不变量之所以成立前提就是我们前面证明的“矩阵按行展开严格递增”。所以严格来说代码里不是“把矩阵当成一维数组”而是矩阵展开后“本来就是一个一维有序数组”。本质上做的是一次标准二分时间复杂度 O(log(m*n))空间复杂度 O(1)。3. 其他可解方案暴力、两次二分、Z字走法3.1 暴力遍历先跑通再谈优化遇到不熟悉的题我习惯先写暴力解跑通再用它做基准去验证优化方案。def searchMatrix(matrix, target): for row in matrix: for val in row: if val target: return True return False双重循环扫一遍时间复杂度 O(m*n)空间 O(1)。在数据量小的时候LeetCode 上也能过但这题明确要求“高效的算法”暴力不是面试官想看到的答案。不过别小看暴力写法的价值先跑通能确认你对题意的理解是对的之后优化出的代码如果和暴力结果对拍一致出错的概率会大大降低。3.2 两次二分先锁行再锁列如果不做一维映射很多人第一反应是“先在行方向上二分找到可能在的行再在列方向上二分”。这个思路完全正确代码也不复杂但有个细节很容易踩坑找候选行时到底怎么定义二分的条件。def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) # 快速剪枝超出矩阵最小值和最大值直接返回 if target matrix[0][0] or target matrix[-1][-1]: return False # 第一次二分找最后一个行首小于 target 的行 top, bottom 0, m - 1 while top bottom: mid top (bottom - top) // 2 if matrix[mid][0] target: return True if matrix[mid][0] target: top mid 1 else: bottom mid - 1 # 循环结束后bottom 是最后一个行首小于 target 的行 row bottom if row 0: return False # 第二次二分在候选行内找 target left, right 0, n - 1 while left right: mid left (right - left) // 2 if matrix[row][mid] target: return True if matrix[row][mid] target: left mid 1 else: right mid - 1 return False很多人在第一次二分这里用的是“找第一个行首大于等于 target 的行再减一”或者用while top bottom的模板结果边界一变就出错。我自己最稳的写法是循环结束后直接取bottom作为候选行。可以代入几个场景验证。假设行首数组是 [1, 3, 5]target 是 4第一次二分中点落在 3 上3 4所以top右移再取中点 55 4所以bottom左移。循环结束时bottom指向 3 所在的下标也就是最后一个行首小于 4 的行。如果 target 比所有行首都大bottom会自然落在最后一行如果 target 比第一个行首还小bottom会变成 -1直接返回 false。这个逻辑想清楚后两次二分的代码也很好写。不过要注意两次二分的复杂度是 O(log m log n)和一维映射的 O(log(m*n)) 在数学上是完全等价的因为log m log n log(m*n)。两者的区别主要是代码组织方式一维映射更简洁两次二分的思路更直观面试时讲哪一种都行。3.3 右上角Z字搜索面向240题的通解还有一个很多人会提到的解法从矩阵右上角出发每次比较当前值和 target决定向左走还是向下走。这个方法在 74 题里也能用但真正的主场是 240 题。def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False row, col 0, len(matrix[0]) - 1 while row len(matrix) and col 0: cur matrix[row][col] if cur target: return True if cur target: row 1 # 当前行最大值都小于 target排除整行 else: col - 1 # 当前列最小值都大于 target排除整列 return False为什么这个走法成立关键在于右上角这个位置很特殊它位于当前行的最右边所以是当前行的最大值同时位于当前列的最上边所以是当前列的最小值。如果 target 比它大那么当前行的所有元素都比 target 小整行可以直接排除于是向下走如果 target 比它小那么当前列的所有元素都比 target 大整列可以直接排除于是向左走。每走一步至少排除一行或一列最坏情况走 mn 步时间复杂度 O(mn)。3.4 三种方案的复杂度对照解法时间复杂度空间复杂度依赖条件适用场景暴力遍历O(m*n)O(1)无本地验证、对拍基准两次二分O(log m log n)O(1)行首有序且行内有序74题可解面试思路直观一维映射二分O(log(m*n))O(1)矩阵展开后全局递增74题最优解右上角Z字搜索O(mn)O(1)每行、每列分别递增240题标准解74题可用刷题时不要只记解法要记住每种解法背后的“前置条件”。比如 Z 字搜索只需要满足“行递增 列递增”不需要行与行之间衔接所以它比一维映射适用面更宽但在满足全局有序的 74 题里它的复杂度不如二分漂亮。4. 边界条件与报错排查这些坑我替你踩了4.1 空矩阵和长度为0的处理顺序我见过不少刚开始刷题的人一上来就写n len(matrix[0])遇到matrix []直接IndexError。正确的顺序是先看行数再看列数if not matrix: return False if not matrix[0]: return Falsenot matrix处理空列表not matrix[0]处理[[]]这种“一行但没列”的情况。注意这两句顺序不能换否则第二句取matrix[0]时仍然可能越界。C 里对应的是matrix.empty()和matrix[0].empty()同样要先判断外层容器。4.2 死循环是怎么写出来的二分法写完后最怕不是找不到答案而是运行起来死活不结束。最常见的死循环写法是while left right: mid (left right) // 2 if matrix[mid // n][mid % n] target: left mid # 这里没有 1 else: right mid当区间收缩到只剩两个元素时mid会一直等于left条件满足后left原地不动循环永远走不出来。我推荐的写法是统一使用闭区间模板while left right收缩时left mid 1、right mid - 1。这个模板每次都把区间真正缩小不需要额外记忆“开区间还是闭区间”的细节。如果你在面试时更习惯写while left right的模板那也可以但必须明确区分“找左边界”和“找右边界”时 mid 的取整方向以及收缩时到底能不能 1/-1。两种模板没有绝对好坏关键是不要在同一个题里来回混用。4.3 下标换算与候选行的易错点症状原因修复IndexError: list index out of range没有判空矩阵先if not matrix or not matrix[0]: return False程序不结束二分收缩写成left mid改成left mid 1保持区间必然收缩结果莫名错误下标换算写成mid // m行号是mid // n列号是mid % n除的是列数两次二分候选行选错行二分模板语义没想清循环结束后bottom是最后一个行首小于 target 的行直接把 240 题当 74 题做混淆了两题的约束条件先确认是否有“全局衔接”条件再决定用哪种算法下标换算这里的错误特别隐蔽。比如一个 3 行 4 列的矩阵mid 5正确的坐标是(1, 1)如果你写成mid // m 1、mid % m 2取到的是(1, 2)这个位置。矩阵元素恰好小的时候可能看不出问题一旦遇到临界数据就直接错。写代码时最好把mid // n和mid % n分别赋值给row和col名字起清楚一眼就能检查出来。5. 变体扩展搜索二维矩阵 II240题5.1 少了那条约束解法就变了LeetCode 240题“搜索二维矩阵 II”是 74 题的经典变体目录里就在附近很多刷 hot100 的朋友会一起做。240 题只保留了两条约束每行从左到右递增每列从上到下递增。它没有“上一行末尾小于下一行开头”这条全局衔接条件。典型例子matrix [ [ 1, 4, 7, 11, 15], [ 2, 5, 8, 12, 19], [ 3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 20, 23, 26, 30] ]第一行末尾是 15第二行开头是 215 明显大于 2展开后序列在行与行之间是“断裂”的。这时候如果按 74 题的思路做一维映射二分就完全不成立了。5.2 为什么240题不能全局二分二分查找能工作的前提是序列有序。一维映射二分把矩阵想象成“下标越大元素越大”这在 74 题成立因为全局衔接条件保证了展开后的序列单调递增但 240 题里这个单调性被破坏下标 4 的元素是 15下标 5 的元素是 2下标更大的元素反而更小。此时二分比较中间值后无法判断 target 到底落在左半边还是右半边“每次排除一半”的推理就失效了。不光是一维映射两次二分在 240 题里也不严谨。因为 target 可能同时出现在多行里你按行首二分找到一个候选行不代表其他行里没有同样的 target。这正好说明一件事刷题不能只背代码必须先判断题目给你的数据结构满足什么性质再选算法。5.3 240题的标准解法同款Z字走法240 题的标准解法就是我前面写过的右上角 Z 字搜索代码完全一样再贴一次方便对照def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False row, col 0, len(matrix[0]) - 1 while row len(matrix) and col 0: if matrix[row][col] target: return True if matrix[row][col] target: row 1 else: col - 1 return False因为 240 题满足“每行递增、每列递增”所以从右上角出发的排除逻辑依然成立当前元素是行的最大值、列的最小值和 target 比较后总能排除一整行或一整列。时间复杂度 O(mn)。这道题的另一个常见起点是左下角逻辑镜像对称可以根据习惯选择。5.4 74题与240题的条件差异一览条件74题240题每行从左到右递增有有每列从上到下递增可由条件推出单独规定上一行末尾小于下一行开头有无矩阵按行展开后全局递增是否一维映射二分可用不可用Z字搜索可用但不是最优标准最优解我的建议是把这两题放在同一天刷先做 74 题再做 240 题体会“同一个搜索任务数据结构性质不同最优算法随之改变”的感觉。这会比单独背题收获大得多。6. 回到hot100这道题的刷题站位与延伸思考6.1 二分专题在hot100里的联动练法Hot 100 里的二分题其实是一个很清晰的小专题除了这一题还包括 33 题搜索旋转排序数组、34 题在排序数组中查找元素的第一个和最后一个位置、35 题搜索插入位置、153 题寻找旋转排序数组中的最小值。这几道题放到一起刷能帮你把二分的各种边界场景都过一遍旋转数组的二分靠的是“两段有序”的观察查找第一个和最后一个位置靠的是“左右边界模板”搜索插入位置靠的是“返回 left 而不是 right”而 74 题靠的是“二维数据一维化”。另外看到热词里有“hot100动态规划”顺嘴说一句动态规划和二分在 Hot 100 里是两个大专题但它们经常交叉出现。比如最长递增子序列的贪心二分优化本质上是在一个有序序列上做二分反过来很多“二分答案”的题目又需要配合动态规划来验证可行性。所以不要把这个题当成孤立的“模板题”它训练的是对有序性的敏感度这种敏感度以后做动态规划里的单调栈优化、斜率优化都会有帮助。6.2 从二维矩阵到一维映射的建模思维一维映射这个技巧并不只在算法题里出现。比如图像处理中一张宽为 width、高为 height 的图片像素在内存里往往就是连续存储的访问坐标 (x, y) 对应的像素时偏移量就是y * width x这和mid // n、mid % n是同一个数学关系。再比如树状数组、线段树里把二维空间压成一维下标或者动态规划里把一个状态压缩成一位数字本质上都是“高维数据线性化”。所以 74 题不是一个孤立的二分题它背后是一种建模思路当数据本身带有序性你能否把它变换成一个更容易处理的结构。面试的时候你能主动说出这层联系会比单纯报出代码好很多。6.3 过来人的刷题经验我个人刷这题不是一遍过的。第一遍只会暴力第二遍会两次二分但候选行老是选错第三遍才真正理解为什么bottom就是最后该查的行。回头看最大的经验是二分查找不要背模板每次写之前先问自己“循环结束后 left 和 right 各自代表什么”把答案写在注释里。能一句话说清楚不变量代码就不会错。还有一个小技巧写完一版解法后用暴力解做对拍。随机生成几个小矩阵把暴力函数和优化函数的结果对比多跑几轮边界问题会自己跳出来。日常刷题时这种“暴力验证优化”的习惯比多刷十道题还管用。下次再遇到二维矩阵相关的搜索题先别急着设计搜索路径停下来问一句这个矩阵展开以后有序吗如果有序二分就是最优解如果只是行和列分别有序那右上角走法马上顶上。这个判断顺序比记住任何一道题的代码都值钱。