Hot100 刷题进度到 17/100 了这道 240. 搜索二维矩阵 II 在我的待刷清单里躺了很久。说句实话第一次看题面的时候我根本没把它当难题——又是搜索、又是二维矩阵按照套路先暴力再二分不就完了吗结果写了一半就发现不对劲普通二分查找的思想根本没法直接套进来因为矩阵虽然行和列各自有序但行与行之间的衔接是乱的。折腾了半天最后真正让我豁然开朗的是那个经典的从右上角出发的思路。这篇就把我完整的理解过程写下来包括三种做法的复杂度账本、为什么右上角能走通、边界条件的坑以及它和 LeetCode 74 这种同名不同命的题到底差在哪里。适合正在刷 Hot100、想系统性整理矩阵搜索类题型的人看也适合面试前临时抱佛脚。1. 题意里最容易误会的一点行列有序不等于全局有序1.1 矩阵的双单调到底给的是什么条件题目描述非常短给出一个 m x n 的矩阵每行的元素从左到右升序每列的元素从上到下升序然后在这个矩阵里搜 target。请注意措辞它并没有说下一行的第一个元素一定比上一行最后一个元素大。举个最直观的例子matrix [ [1, 4, 7], [2, 5, 8], [3, 6, 9] ]行从左到右升序第 1 行 1→4→7第 2 行 2→5→8没问题。列从上到下升序第 0 列 1→2→3第 1 列 4→5→6也没问题。但如果你把整个矩阵当成一个一维有序数组来看立刻就会乱套7 是矩阵第一行的最后一个元素而它后面跟着的是第二行的第一个元素 22 比 7 小。所以展平后全局递增这个性质根本不存在。这里我是吃过亏的。最早我想的是取矩阵中心点二分把矩阵切成四块递归搜理论上能写但界限极其别扭。核心原因就在于普通二分查找依赖的是一个比较结果能排除掉一半候选区间的全局单调性而这个矩阵只有局部单调性去掉中心元素之后你没法保证左上角和右下角这两个子矩阵之间有任何可比关系。1.2 为什么最关键的信息藏在右上角而不是左上角我后来换了个角度想问题矩阵里有四个角落它们的信息量是完全不同的。左上角它比右边大不它比右边小它比下边小。左上角是整个矩阵的最小值它只知道我太小了但你分不清该往右走还是往下走。右下角同理它是最大值只知道我太大了但你也分不清该往左走还是往上走。左下角向左变小向上变小两个方向都在变小同样没法二分。右上角每个元素右边的值都比它大下面的值也都比它大而左边的值比它小。换句话说站在右上角这个位置看向左是唯一变小的方向向下是唯一变大的方向。这就有意思了每次比较后方向选择是唯一的。如果 target 比当前值小那只能往左走如果 target 比当前值大那只能往下走。这种一进一出的结构其实已经把矩阵隐式地变成了一棵二叉搜索树把每个格子当节点它的左孩子是左边紧挨着的格子右孩子是下面紧挨着的格子。右上角就是整棵树的根节点。为了说服自己我当时拿上面那个 3x3 矩阵画了一下从右上角的 7 出发左孩子是 4下一个左孩子是 1下一个右孩子是 2下一个右孩子是 3……整棵树恰好覆盖了矩阵的所有元素而且满足左小右大的 BST 性质。那一刻我才明白这道题本质不是在搜索矩阵是在遍历一棵按特殊规则生成出来的二叉搜索树。1.3 一个反例彻底断了全局二分的念想如果面试官问你为什么不能把矩阵当成排序数组直接二分最好的回答不是背结论而是直接甩一个反例。以 1.1 小节那个矩阵为例假设 target 8你按常规一维二分思路先把整个二维数组映射成[1, 2, 3, 4, 5, 6, 7, 8, 9]这种顺序第一次取中间位置 5 没问题5 8于是你跳向右半边。但右半边是从 6 开始的子序列它确实包含 8看起来好像能成立——换个 target 就露馅了target 2映射数组中间是 55 2跳到左半边搜[1, 2, 3, 4]也能找到 2。但这些成功纯粹是巧合因为示例矩阵太小、太工整。换一个稍微复杂的矩阵比如[[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16]]你按行展平得到[1, 4, 7, 11, 2, 5, 8, 12, 3, 6, 9, 16]这个序列根本不是有序的11 后面跟着 2。如果 target 11你想用二分就必须先对整个序列排序一排序元素的原始位置信息就全丢了你搜到的下标对矩阵来说毫无意义。所以矩阵全局二分这条路从一开始就是死的。2. 从暴力到 O(mn)三个层次的方案和复杂度账本2.1 暴力双重循环先立一个基线遇到搜索题我习惯先写一版最无脑的暴力不是为了交差而是为了确认自己对边界的理解没跑偏。这道题的暴力写法连脑筋都不用动public boolean searchMatrix(int[][] matrix, int target) { for (int i 0; i matrix.length; i) { for (int j 0; j matrix[0].length; j) { if (matrix[i][j] target) { return true; } } } return false; }时间复杂度 O(mn)空间复杂度 O(1)。这个版本没有任何利用矩阵结构但它是后面所有优化的参照物。跑一些小样例也能帮你验证题目说的行列升序到底长什么样。面试里你直接写这个肯定不行但作为思考起点完全合格。2.2 逐行二分利用了一半的条件但不是最优既然每一行都是有序数组那么很自然的想法是遍历每一行对每一行做一次二分查找。这个思路利用了行内有序复杂度 O(m log n)。public boolean searchMatrix(int[][] matrix, int target) { for (int[] row : matrix) { int left 0; int right row.length - 1; while (left right) { int mid left (right - left) / 2; if (row[mid] target) { return true; } else if (row[mid] target) { left mid 1; } else { right mid - 1; } } } return false; }这个版本看着挺像回事也确实是许多资料里给出的答案之一。但你要注意一点它完全没用上列也升序这个条件。也就是说如果矩阵的列完全乱序这个代码依然能跑。既然题目额外给了列有序那就说明存在更好的解法挖掘这个信息才是这题真正的考点。还有一种中间状态如果 m 和 n 的数量级差很多比如 m100000、n3这时候逐行二分的 O(m log n) 可能比右上角 O(mn) 更合适因为在常数项的比拼中二分查找的 log n 远小于 n。这是工程上的取舍面试中可以主动提一嘴显得你不仅会做题还懂分析数据规模。2.3 右上角搜索把两个方向都在变大扭转成一升一降最终要掌握的方案就是从右上角开始搜索。算法的过程极其简单初始位置设为第一行、最后一列也就是row 0col n - 1。把当前格子的值和 target 比较。如果相等直接返回 true。如果当前值大于 target说明当前列这一块都太大了向左移动一列col--。如果当前值小于 target说明当前行这一块都太小了向下移动一行row。如果越界返回 false。这个思路的核心魔力在于右上角的格子向右看没有元素向下看全是比它大的向左看全是比它小的。所以每一次比较都能把当前所在的这一列或者当前所在的这一行彻底排除掉而不是像二分那样只能排除半个数组。走一步排除一行再走一步又排除一列。总共最多走 mn 步矩阵就被排除光了。2.4 三个方案的复杂度账本我整理了一张对比表面试前直接背这一页就够了方案时间复杂度空间复杂度利用矩阵性质适用场景暴力双重循环O(mn)O(1)完全没利用矩阵极小或用来做正确性对照逐行二分O(m log n)O(1)只用行有序m 很大而 n 很小时反而有优势右上角搜索O(mn)O(1)同时利用行和列有序大多数情况下的最优解面试首选这里有个容易忽略的点右上角搜索的最坏情况步数是 mn而不是 m*n。也就是说即使 target 不存在整个搜索过程也不过是从右上角一路走到左下角每次要么 row1要么 col-1两个方向累计消耗。这个上界一定要能脱口而出因为面试官大概率会追问你凭什么说它是 O(mn)。3. 向右上角走的每一步都在剪枝单调性推演和严格论证3.1 为什么当前值比 target 大就一定向左而不是向上很多人背代码会背但被问为什么当前值大于 target 时要 col-- 而不是 row--就愣住了。这里必须结合矩阵的列升序性质来讲。关键点是当前格子所在的这一列从当前行往下所有元素都大于等于当前值。因为列是升序的越往下越大。所以如果当前值已经大于 target那么当前列中下面所有格子必然也大于 target它们全都不可能等于 target。这一整列就直接报废了于是我们向左移动换到前一列重新判断。但为什么不能向上移动呢因为上面那些格子已经在之前的步骤里被排除过了你在搜索路线上不会往回走。向上移动会回到已经判定过不可能包含 target的区域没有意义。搜索路径的方向只能是在候选区域的内部移动而右上角起步、向左和向下这两个方向都指向未检查过的区域。对称地如果当前值小于 target由于行是升序的当前行左侧的所有元素都小于等于当前值它们也都不可能等于 target所以这一整行报废于是向下移动。向上、向右都已经没有未探索的价值。3.2 用题目示例当场把路径走一遍LeetCode 原题示例矩阵是matrix [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]先说 target 5 的查找过程。起点matrix[0][4] 15。15 5当前列整列下方是 19、22、24、30全都大于 5排除第 4 列col 3。matrix[0][3] 11 5第 3 列下方是 12、16、17、26排除第 3 列col 2。matrix[0][2] 7 5第 2 列下方是 8、9、14、23排除第 2 列col 1。matrix[0][1] 4 5第 0 行左侧是 1整行都小于 5排除第 0 行row 1。matrix[1][1] 5相等返回 true。一共走了 5 步正好是一个折线路径。再看 target 20 的失败过程。matrix[0][4] 15 20排除第 0 行row 1。matrix[1][4] 19 20排除第 1 行row 2。matrix[2][4] 22 20排除第 4 列col 3。matrix[2][3] 16 20排除第 2 行row 3。matrix[3][3] 17 20排除第 3 行row 4。matrix[4][3] 21 20排除第 3 列col 2。matrix[4][2] 23 20排除第 2 列col 1。matrix[4][1] 13 20排除第 4 行row 5。row 5越界返回 false。注意到没这个失败过程虽然走了 8 步但它始终在缩小一个候选子矩阵的范围候选子矩阵的行范围是[row, m-1]、列范围是[0, col]。每一步排除当前候选区间的顶行或右列于是行下界不断下移或列上界不断左移。这种每步消除一条整边的结构就是这道题和普通二分最大的差异点。3.3 严格证明为什么这个剪枝永远不会漏掉正确答案如果想把思路讲得滴水不漏可以这样表述假设 target 存在于矩阵中且它落在某个位置(r*, c*)。我们维护一个候选区域行号在 [row, 最后一行] 之间列号在 [0, col] 之间。初始时row 0col 最后一列候选区域覆盖整个矩阵所以 target 一定在这里面。每次比较当前右上角元素matrix[row][col]如果matrix[row][col] target由于该行从左到右升序第 row 行的全部元素都小于等于当前值所以都小于 target。这一行不可能有 target候选区域的上边界下移row。target 仍在新的候选区域内。如果matrix[row][col] target由于该列从上到下升序第 col 列从 row 行往下所有元素都大于等于当前值所以都大于 target。这一列不可能有 target候选区域的右边界左移col--。target 仍在新的候选区域内。所以不论走多少步只要 target 存在它就从未被排除出候选区域。最终要么在某一步遇到相等的格子要么候选区域变空得出不存在的结论。这就是正确性的完整逻辑链条面试时能把这个不变量讲清楚比背十遍代码都管用。4. 代码落地与实测中容易踩的三个低级错误4.1 主流语言的实现Java 版本在实际编码时我更推荐把初始判断放在前面的写法省得后面纠结二维数组为空的问题。public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0] null || matrix[0].length 0) { return false; } int rows matrix.length; int cols matrix[0].length; int row 0; int col cols - 1; while (row rows col 0) { int cur matrix[row][col]; if (cur target) { return true; } else if (cur target) { row; } else { col--; } } return false; }注意 while 循环的条件是row rows col 0不是。因为col是索引初始值是cols - 1当它减到 -1 时说明所有列都被排除row加到最后一行1 时说明所有行都被排除。我把cur target写在前面、col--兜底逻辑顺序清晰也方便调试时打断点观察 row 和 col 的变化。4.2 简洁的 Python 版本Python 写出来更短但容易在 while 条件上犯迷糊。def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False rows, cols len(matrix), len(matrix[0]) row, col 0, cols - 1 while row rows and col 0: cur matrix[row][col] if cur target: return True if cur target: row 1 else: col - 1 return FalsePython 的not matrix or not matrix[0]既能拦掉空矩阵也能拦掉只有 0 列的矩阵。我个人习惯在本地测试时直接打印每一步的(row, col, matrix[row][col])把搜索路径打出来对理解算法帮助极大。4.3 低级错误一把空矩阵判断写得太随意有一次我在快速写代码时只写了if (matrix.length 0)忘了判断matrix[0].length 0。结果遇到matrix new int[0][0]时能过遇到matrix new int[0][5]也会被matrix.length 0拦住但遇到matrix new int[2][0]这种有行无列的怪形状时matrix[0]是存在的空数组下一行取matrix[0].length得到 0代码逻辑上不会崩但循环一进来就会因为col -1而跳过。其实这种情况更稳妥的做法是统一把没有有效元素都算空矩阵也就是写成if (matrix null || matrix.length 0 || matrix[0].length 0)。这也是为什么我在 4.1 里加上了matrix[0] null的判断防止拿到null数组。4.4 低级错误二想着用 DFS 或者记忆化搜索还有一次我把问题想复杂了觉得从右上角执行搜索有点类似迷宫遍历于是写出了带 visited 数组的 DFS 版本。结果不仅代码长度翻倍还引入了一堆与剪枝无关的额外状态。其实这道题的搜索路径是唯一的、单调的根本不需要回溯。DFS 适合的是无法确定下一步该走哪条路、需要尝试多条路径的场景而这里每一步方向已经被大小关系确定死了。过度设计是刷题里最常见的自我感动写完之后再回头看最简单的循环就是最优解。4.5 低级错误三忽略重复元素对升序的容忍度题目说每行、每列升序但没严格说严格递增。如果你在一道变形题里遇到重复元素比如矩阵里有两个 5右上角搜索一样可以工作因为我们的排除逻辑用的是大于和小于遇到相等直接返回。凡是包含等于 target 的格子都不会被当前步的错误方向排除掉。这一点可以在面试时主动提出来表示你注意到题目对升序的定义不一定是严格递增。5. 别和 74 题弄混两道搜索二维矩阵的条件、做法、复杂度全对比5.1 LeetCode 74条件更强一维二分直接可用LeetCode 74 的题目名叫搜索二维矩阵和 240 只差一个数字但条件天差地别。74 题矩阵满足两个条件每一行从左到右升序每一行的第一个整数都大于上一行的最后一个整数。也就是说74 题里的矩阵可以按行展平成一个严格递增的一维数组因为它保证了前一行末尾 后一行开头。这时候你完全可以把二维坐标映射成一维下标做一次标准二分查找时间复杂度 O(log(mn))。很多初学者会混淆这两题原因就是题目名太像、矩阵也都是有序的。但它们背后的单调性强度完全不同74 题是全局强序240 题是行列弱序。74 题可以看作 240 的超强特例。5.2 做题时的选择顺序刷题复盘我给自己定的规则是看到搜索二维矩阵先确认条件行内升序 列内升序还是行内升序 跨行也递增如果是跨行也递增直接一维二分代码最短。如果只保证行列各自升序优先右上角搜索O(mn)。如果行列数量悬殊比如行数非常少、列数非常多逐行二分的 O(m log n) 也许才是真实工程场景下更快的方案。这里有个实际例子如果 m100、n100000那么右上角搜索最坏要走 100100 步而逐行二分最多 100 * 17 1700 次比较。虽然理论上都是多项式复杂度但常数差异在极端数据下非常明显。LeetCode 的判题数据通常没那么极端但这道题确实是对按数据规模选算法这个意识的很好训练。5.3 同族题目的延伸1351 和 378理解了右上角搜索之后很多矩阵类题目会变得豁然开朗。比如 LeetCode 1351统计有序矩阵中的负数个数。矩阵每行每列都是降序的你从右上角出发如果当前值是负数那么整列往下的元素都会更小全是负数直接累加如果当前值不是负数当前行往左的元素更大往左移动。思路几乎和 240 一模一样只是把等于变成了统计复杂度同样 O(mn)。再比如 LeetCode 378有序矩阵中第 K 小的元素。这道题除了用堆来做也可以对值域做二分然后在矩阵里用右上角走法统计有多少元素小于等于 mid通过调整上下界逼近第 K 小。这里的核心组件依然是 240 题教给我们的按行列有序矩阵快速计数能力。可以说240 是矩阵单调性题型的地基。还有一个面试里可能出现的变体如果题目给出的矩阵无限大没有明确的行列边界你该怎么搜目标值这时候可以从左上角开始指数倍增地扩大搜索范围先在有限的子矩阵内定位再用右上角搜索的思想收缩。虽然真实面试很少考这种但做 240 时想一下这种变体对理解边界信息和方向选择会有更深的感觉。6. Hot100 里这道题该怎么消化我的刷题复盘记录6.1 我把它归进了单调性与剪枝这一类Hot100 题目很多单纯按编号刷一遍很容易忘。我的习惯是刷完当天就用一张卡片把它归类。240 搜二维矩阵 II 在我卡片上的分类是单调性 候选区域剪枝。和它同卡片的还有 1658 将 x 减到 0 的最小操作数滑动窗口、15 三数之和双指针夹逼、以及 11 盛最多水的容器双指针移动短边。这些题的核心共同点都是通过某个单调性保证每一步能排除一段候选区间。把这一类放在一起复盘比单独背一道题要有用得多。6.2 我的三次刷题记录第一次刷暴力逐行二分过了以为完事。隔两周重刷忘记右上角思路又写了逐行二分。第三次刷前我先在纸上画了 3x3 矩阵对应的 BST把根节点、左子树、右子树标出来然后默写右上角搜索一次通过。这个经历说明难点根本不是代码而是为什么这个方向选择是对的。如果你只看答案不看证明下次遇到原题还是会卡。我会在代码旁边留一段注释写的是候选区域是 [row..m-1] x [0..col]当前值是右上角若 curtarget 排除顶行否则排除右列。这个注释既是给未来的自己看也是面试时讲思路的小抄。6.3 面试中两个加分的小习惯第一写代码之前先复述题目条件尤其是点出矩阵是行升序加列升序不等于全局升序这个关键差异。这会让面试官知道你真的理解了题意而不是上来就默模板。第二讲复杂度时要讲清楚为什么最坏是 O(mn) 而不是 O(mn)因为每次循环 row 只会加一、col 只会减一两者各自的增减次数加起来不超过 mn。把这两个条件的变化范围说出来复杂度分析就非常可信。第三个经验是关于自测用例的。我提交前习惯先跑这么几个用例空矩阵、单行矩阵[[1, 3, 5]]、单列矩阵[[1], [3], [5]]、以及 target 是矩阵最小值或最大值的情况。这些用例能一次性覆盖大多数 while 循环边界 bug。224 题这类边界情况尤其多在 240 题上养成这个习惯后面刷矩阵类题目都能受益。最后说个我自己的小体会做搜索类题目时先别急着搜代码先在草稿纸上把每一步能排除什么区域画出来。只要你画得出排除过程代码就自然而然写对了。240 这道题的价值不在于它有多难而在于它用最简单的方式告诉你矩阵有序性怎么用、方向怎么选、证明怎么做。把这道题吃透后面遇到矩阵搜索变体你会觉得特别踏实。
