题目描述
思路解析
一句话答案：LeetCode 240 搜索二维矩阵 II 的高效解法是从右上角出发的阶梯搜索：右上角元素同时是本行最大、本列最小，它比 target 大就左移排除一整列，比 target 小就下移排除一整行，每比较一次必砍掉一行或一列，最多走 m+n 步，时间 O(m+n)、空间 O(1)。
这道题真正在问什么
给一个 m 行 n 列的矩阵，每行从左到右升序、每列从上到下升序，判断 target 是否在其中。要小心它和「搜索二维矩阵 I」的区别：这里只有行、列各自有序，整体并不能摊平成一个有序的一维数组——上一行的末尾未必小于下一行的开头，所以把整个矩阵当一维序列做一次全局二分是行不通的。
暴力和逐行二分分别卡在哪
逐格扫描要 O(m×n)，完全没用上有序性。稍好的做法是对每一行做二分查找，O(m·log n)——它用了行有序，却把列有序整个浪费了。两个维度的有序信息都在手上，理想的算法应该做到「一次比较就排除一大片」。于是问题变成：站在哪个位置比较，才能让「比 target 大」和「比 target 小」各自指向一个确定无疑的排除方向？
为什么偏偏要从右上角出发
右上角的元素有个独一无二的身份：它是所在行的最大值，同时是所在列的最小值。拿它和 target 比，两种结果都有干脆的结论——它比 target 大，说明它下方整列只会更大，这一列可以整列扔掉，指针左移；它比 target 小，说明连本行最大的都不够，这一行整行扔掉，指针下移。相比之下，左上角是行列双最小、右下角是行列双最大，比较结果无论偏大偏小都无法唯一确定该往哪走，一格都排除不了。左下角与右上角对称（本列最大、本行最小），同样可行。
每一步的排除为什么都不冤枉
这个走法可以看成拿单调性做贪心排除：每次比较后被扔掉的那一行或一列，有升序性质背书，绝不可能藏着 target；而 target 若存在，必然还留在剩余的子矩阵里——循环全程保持「候选区域始终包含答案（若答案存在）」这个不变量。指针只会向左或向下、永不回头，所以既不漏查也不绕圈，直到命中返回 true，或走出矩阵边界宣告不存在。
复杂度怎么数，边界在哪里
每一步要么列指针减一、要么行指针加一：列最多减 n 次、行最多加 m 次，总步数不超过 m+n，时间 O(m+n)，空间 O(1)，只用两个指针。实现上的两个坑：循环条件必须在指针越界（列减到负数、行加到 m）时停下并返回 false；比较后的移动方向别写反——比 target 大是左移砍列、比 target 小才是下移砍行，写反会把可能藏着答案的区域整片扔掉。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住右上角的妙处：它同时是「本行最大、本列最小」。比 target 大就往左砍一列，比 target 小就往下砍一行，相等就命中。
指针放在右上角 (0,4)，那一格的值是 15。准备拿它和 target=18 比一比。
在 (0,4) 看到 15，和 target=18 比：它更小。它是这一行里最大的都还比 target 小，整行没戏，往下挪一格。
刚才那一行整行排除（变灰），指针下移一行，来到 (1,4)，值是 19，继续比。
在 (1,4) 看到 19，和 target=18 比：它更大。它是这一列里最小的都已经比 target 大，整列没戏，往左挪一格。
刚才那一列整列排除（变灰），指针左移一列，来到 (1,3)，值是 12，继续比。
在 (1,3) 看到 12，和 target=18 比：它更小。它是这一行里最大的都还比 target 小，整行没戏，往下挪一格。
刚才那一行整行排除（变灰），指针下移一行，来到 (2,3)，值是 16，继续比。
在 (2,3) 看到 16，和 target=18 比：它更小。它是这一行里最大的都还比 target 小，整行没戏，往下挪一格。
刚才那一行整行排除（变灰），指针下移一行，来到 (3,3)，值是 17，继续比。
在 (3,3) 看到 17，和 target=18 比：它更小。它是这一行里最大的都还比 target 小，整行没戏，往下挪一格。
刚才那一行整行排除（变灰），指针下移一行，来到 (4,3)，值是 26，继续比。
在 (4,3) 看到 26，和 target=18 比：它更大。它是这一列里最小的都已经比 target 大，整列没戏，往左挪一格。
刚才那一列整列排除（变灰），指针左移一列，来到 (4,2)，值是 23，继续比。
在 (4,2) 看到 23，和 target=18 比：它更大。它是这一列里最小的都已经比 target 大，整列没戏，往左挪一格。
刚才那一列整列排除（变灰），指针左移一列，来到 (4,1)，值是 21，继续比。
在 (4,1) 看到 21，和 target=18 比：它更大。它是这一列里最小的都已经比 target 大，整列没戏，往左挪一格。
刚才那一列整列排除（变灰），指针左移一列，来到 (4,0)，值是 18，继续比。
在 (4,0) 看到 18，和 target=18 比：正好相等，找到了！
(4,0) 这一格就是 target=18（标绿），返回 true。一共走了 9 步就锁定了它。
回看整趟：蓝色是走过比较过的格子，灰色是被整行整列排除的区域，绿色就是命中的 target。一共 9 步，远小于 5×5=25 格。
三个高频追问：O(m+n) 的来历、和按行二分的对比、以及左下角的对称解法。
参考代码
def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False r, c = 0, len(matrix[0]) - 1 # 从右上角出发 while r < len(matrix) and c >= 0: v = matrix[r][c] if v == target: return True elif v > target: c -= 1 # 太大，砍掉这一列 else: r += 1 # 太小，砍掉这一行 return False复杂度
- 时间：O(m+n)，每一步必定砍掉一整行或一整列，最多走 m+n 步
- 空间：O(1)，只用 r、c 两个指针，不开额外空间
易错点
面试追问把动画讲成自己的话
追问为什么时间复杂度是 O(m+n) 而不是 O(m×n)？
追问能不能对每一行做二分查找？复杂度多少？
追问从左下角出发可以吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一个排列
LeetCode 31 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题