企业官网建设流程全解析

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 是矩阵第一行的最后一个元素，而它后面跟着的是第二行的第一个元素 2，2 比 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，映射数组中间是 5，5 > 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(m+n)：三个层次的方案和复杂度账本

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 的数量级差很多，比如 m=100000、n=3，这时候逐行二分的 O(m log n) 可能比右上角 O(m+n) 更合适，因为在常数项的比拼中二分查找的 log n 远小于 n。这是工程上的取舍，面试中可以主动提一嘴，显得你不仅会做题，还懂分析数据规模。

2.3 右上角搜索：把"两个方向都在变大"扭转成"一升一降"

最终要掌握的方案，就是从右上角开始搜索。

算法的过程极其简单：

1. 初始位置设为第一行、最后一列，也就是row = 0，col = n - 1。
2. 把当前格子的值和 target 比较。
3. 如果相等，直接返回 true。
4. 如果当前值大于 target，说明当前列这一块都太大了，向左移动一列：col--。
5. 如果当前值小于 target，说明当前行这一块都太小了，向下移动一行：row++。
6. 如果越界，返回 false。

这个思路的核心魔力在于：右上角的格子向右看没有元素，向下看全是比它大的，向左看全是比它小的。所以每一次比较，都能把"当前所在的这一列"或者"当前所在的这一行"彻底排除掉，而不是像二分那样只能排除半个数组。走一步，排除一行；再走一步，又排除一列。总共最多走 m+n 步，矩阵就被排除光了。

2.4 三个方案的复杂度账本

我整理了一张对比表，面试前直接背这一页就够了：

这里有个容易忽略的点：右上角搜索的最坏情况步数是 m+n，而不是 m*n。也就是说即使 target 不存在，整个搜索过程也不过是"从右上角一路走到左下角"，每次要么 row+1，要么 col-1，两个方向累计消耗。这个上界一定要能脱口而出，因为面试官大概率会追问"你凭什么说它是 O(m+n)"。

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 = 0，col = 最后一列，候选区域覆盖整个矩阵，所以 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 False

Python 的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 题矩阵满足两个条件：

1. 每一行从左到右升序；
2. 每一行的第一个整数都大于上一行的最后一个整数。

也就是说，74 题里的矩阵可以按行展平成一个严格递增的一维数组，因为它保证了"前一行末尾 < 后一行开头"。这时候你完全可以把二维坐标映射成一维下标，做一次标准二分查找，时间复杂度 O(log(mn))。

很多初学者会混淆这两题，原因就是题目名太像、矩阵也都是有序的。但它们背后的单调性强度完全不同：74 题是"全局强序"，240 题是"行列弱序"。74 题可以看作 240 的超强特例。

5.2 做题时的选择顺序

刷题复盘我给自己定的规则是：

• 看到"搜索二维矩阵"先确认条件：行内升序 + 列内升序，还是行内升序 + 跨行也递增？
• 如果是跨行也递增，直接一维二分，代码最短。
• 如果只保证行列各自升序，优先右上角搜索，O(m+n)。
• 如果行列数量悬殊，比如行数非常少、列数非常多，逐行二分的 O(m log n) 也许才是真实工程场景下更快的方案。

这里有个实际例子：如果 m=100、n=100000，那么右上角搜索最坏要走 100100 步；而逐行二分最多 100 * 17 = 1700 次比较。虽然理论上都是多项式复杂度，但常数差异在极端数据下非常明显。LeetCode 的判题数据通常没那么极端，但这道题确实是对"按数据规模选算法"这个意识的很好训练。

5.3 同族题目的延伸：1351 和 378

理解了右上角搜索之后，很多矩阵类题目会变得豁然开朗。

比如 LeetCode 1351，统计有序矩阵中的负数个数。矩阵每行每列都是降序的，你从右上角出发，如果当前值是负数，那么整列往下的元素都会更小，全是负数，直接累加；如果当前值不是负数，当前行往左的元素更大，往左移动。思路几乎和 240 一模一样，只是把"等于"变成了"统计"，复杂度同样 O(m+n)。

再比如 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]，当前值是右上角；若 cur<target 排除顶行，否则排除右列"。这个注释既是给未来的自己看，也是面试时讲思路的小抄。

6.3 面试中两个加分的小习惯

第一，写代码之前先复述题目条件，尤其是点出"矩阵是行升序加列升序，不等于全局升序"这个关键差异。这会让面试官知道你真的理解了题意，而不是上来就默模板。

第二，讲复杂度时要讲清楚为什么最坏是 O(m+n) 而不是 O(mn)：因为每次循环 row 只会加一、col 只会减一，两者各自的增减次数加起来不超过 m+n。把这两个条件的变化范围说出来，复杂度分析就非常可信。

第三个经验是关于自测用例的。我提交前习惯先跑这么几个用例：空矩阵、单行矩阵[[1, 3, 5]]、单列矩阵[[1], [3], [5]]、以及 target 是矩阵最小值或最大值的情况。这些用例能一次性覆盖大多数 while 循环边界 bug。224 题这类边界情况尤其多，在 240 题上养成这个习惯，后面刷矩阵类题目都能受益。

最后说个我自己的小体会：做搜索类题目时，先别急着搜代码，先在草稿纸上把"每一步能排除什么区域"画出来。只要你画得出排除过程，代码就自然而然写对了。240 这道题的价值不在于它有多难，而在于它用最简单的方式告诉你：矩阵有序性怎么用、方向怎么选、证明怎么做。把这道题吃透，后面遇到矩阵搜索变体，你会觉得特别踏实。