CS-Notes 剑指 Offer：二维数组中的查找——行列均有序矩阵的 O(M+N) 阶梯查找

本文围绕 notes/4. 二维数组中的查找.md 讲解一道经典的剑指 Offer 面试题：在「每行从左到右递增、每列从上到下递增」的二维数组中判断目标值是否存在。读完本篇，你将掌握为什么从右上角出发的阶梯查找可以在 O(M+N) 时间内解决该问题、每一步决策背后的不变量是什么，并能正确处理空数组等边界条件，同时了解它与逐行二分、回溯搜索等其它矩阵查找手段的适用边界。

一、题目描述

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

原文档给出的示例矩阵如下：

Consider the following 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]
]

Given target = 5,  return true.
Given target = 20, return false.

题目的性能要求是：时间复杂度 O(M + N)，空间复杂度 O(1)，其中 M 为行数，N 为列数。这道题收录在 CS-Notes 的剑指 Offer 题解 - 数组与矩阵分类中，是该系列第 4 题。

二、朴素方案为什么不够好

在展开正解之前，先看清两类"直觉方案"的代价，这样更能理解正解的价值：

1. 暴力遍历：逐一检查 M×N 个元素，时间复杂度 O(M×N)，没有利用任何排序信息；
2. 逐行二分查找：对每一行分别做二分查找（二分查找的标准实现与边界处理可参考 Leetcode 题解 - 二分查找），总复杂度为 O(M × log N)。

逐行二分虽然已经比暴力快，但没有达到题目要求的 O(M + N)。问题的突破口在于同时利用行有序和列有序这两个约束，让每一次比较都能直接划掉一整行或一整列。

三、核心思路：从右上角出发的阶梯查找

原文档的解题思路可以概括为两句话：

该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来快速地缩小查找区间，每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。

为什么偏偏是右上角

考虑矩阵四个角的性质。以右上角元素 matrix[0][cols-1] 为例，由题目约束可知：

• 它的行从左到右递增，因此它是所在行的最大值；
• 它的列从上到下递增，因此它是所在列的最小值。

这意味着它与 target 比较后，结论是二选一的、无歧义的：

• target < matrix[r][c]：target 只可能出现在当前列的左边（当前列从上到下递增，当前元素已是该列最小值且仍大于 target），于是整列排除，c--；
• target > matrix[r][c]：target 只可能出现在当前行的下边（当前行从左到右递增，当前元素已是该行最大值且仍小于 target），于是整行排除，r++；
• target == matrix[r][c]：直接返回 true。

对比之下，从左上角出发则无法决策：左上角元素比它大的数既可能在右边也可能在下边，一次比较不能确定排除哪一条；从左下角出发的逻辑与右上角完全对称（等于时返回、小于时 r++、大于时 c++ 的镜像形式），同样可行，但右上角是最常用的表述方式。

整个搜索过程中存在一个清晰的不变量：target 若存在，必然位于当前元素左下角的矩形区域内；每移动一步，候选区域就收缩掉一行或一列，搜索路径呈阶梯状，因此该方法常被称为"阶梯查找"（staircase search）。

示例走查

用题目给出的 5×5 矩阵验证两种典型结果。

target = 5（存在）：

步	当前位置 (r, c)	当前值	决策
1	(0, 4)	15	5 < 15，排除第 4 列，c--
2	(0, 3)	11	5 < 11，c--
3	(0, 2)	7	5 < 7，c--
4	(0, 1)	4	5 > 4，排除第 0 行，r++
5	(1, 1)	5	相等，返回 true

target = 20（不存在）：

步	当前位置 (r, c)	当前值	决策
1	(0, 4)	15	20 > 15，r++
2	(1, 4)	19	20 > 19，r++
3	(2, 4)	22	20 < 22，c--
4	(2, 3)	16	20 > 16，r++
5	(3, 3)	17	20 > 17，r++
6	(4, 3)	23	20 < 23，c--
7	(4, 2)	21	20 < 21，c--
8	(4, 1)	21	20 < 21，c--
9	(4, 0)	18	20 > 18，r++ 后越界，返回 false

两条路径都只走了常数次比较，且从未回头重复比较任何元素。

四、代码实现

下面是原文档给出的 Java 实现，并补充了注释：

public boolean Find(int target, int[][] matrix) {
    // 边界处理：矩阵为 null、0 行或 0 列时直接返回 false
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return false;
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = cols - 1; // 从右上角开始
    while (r <= rows - 1 && c >= 0) {
        if (target == matrix[r][c])
            return true;              // 命中
        else if (target > matrix[r][c])
            r++;                       // target 更大，当前行全部小于 target，排除本行
        else
            c--;                       // target 更小，当前列全部大于 target，排除本列
    }
    return false; // r 或 c 越界，说明候选区域已空
}

实现要点说明：

• 边界防护：matrix == null || matrix.length == 0 || matrix[0].length == 0 覆盖了"传入 null"、"0 行"、"0 列"三种退化输入，避免后续取 matrix[0].length 或 matrix[r][c] 时抛出空指针/越界异常；
• 循环终止条件 r <= rows - 1 && c >= 0：只要 r 下移到矩阵下方或 c 左移到矩阵左方，候选区域即为空，搜索必然失败，返回 false；
• 每一步至多比较 3 次（相等/大于/小于），但注意 r++ 与 c-- 互斥，整个循环中 r 最多增加 rows 次、c 最多减少 cols 次，因此循环总次数有明确上界。

五、复杂度分析与正确性

时间复杂度 O(M + N)：设 M 为行数、N 为列数。r 从 0 起步、最多执行 M-1 次 r++；c 从 N-1 起步、最多执行 N-1 次 c--。两者之和即总比较次数，最坏不超过 M + N - 1 次，故时间复杂度为 O(M + N)。这一界比逐行二分的 O(M × log N) 更紧：例如 1000×1000 的矩阵，前者最坏约 1999 次比较，后者约 10000 次。

空间复杂度 O(1)：算法只使用 r、c、rows、cols 等常数个变量，没有额外的递归栈或辅助数组。

正确性依据：由前文的不变量，target 若存在则始终落在"当前元素左下角的矩形区域"内；每次比较要么命中，要么把不可能包含 target 的整行/整列移出候选区域。由于矩阵中的值行、列均严格递增，被排除行/列中确实不可能存在 target，因此当 r、c 越界时（候选区域为空）返回 false 是完备的。

六、变体与延伸讨论

变体：统计或枚举 target 的出现次数

若矩阵允许重复值（行、列非严格递增），可以在同一框架上稍加改动来统计 target 的个数：命中时不再立即返回，而是同时 r++ 且 c-- 沿对角线移动——因为 target 若再次出现，只可能出现在当前元素的正下方或正左方区域，二者并集恰好由对角线移动逐步覆盖：

public int count(int target, int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return 0;
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = cols - 1, cnt = 0;
    while (r < rows && c >= 0) {
        if (target == matrix[r][c]) {
            cnt++;
            r++;  // 命中后沿对角线移动，继续搜索左下区域
            c--;
        } else if (target > matrix[r][c]) {
            r++;
        } else {
            c--;
        }
    }
    return cnt;
}

该变体依然保持 O(M + N) 时间与 O(1) 空间。

适用前提：两个有序约束缺一不可

阶梯查找成立的前提是行有序与列有序同时成立。可以推断：如果题目只保留"每行从左到右递增"而去掉列约束（即 LeetCode 常见的 Search a 2D Matrix II 之外的变体场景），从右上角向下/左移动时无法保证排除整列的正确性，算法必须退化为逐行二分，复杂度回到 O(M × log N)。反过来，若只有列有序，则可改为逐列二分。理解这一前提，能避免把本方法误用到不满足条件的矩阵上。

仓库中的相关题目

矩阵类问题在 剑指 Offer 题解 - 目录 的"数组与矩阵"分类中成组出现，与本题思路互补的还有：

• 12. 矩阵中的路径：在无序矩阵上按字符搜索路径，无法利用任何有序性，只能使用回溯法（backtracking）穷举并回退状态，是本题"利用有序性剪枝"的反面教材；
• 29. 顺时针打印矩阵：同样操作二维数组，但目标是用双指针控制四边界逐层收缩，其"边界收缩"的思维与阶梯查找的"行列排除"同源；
• Leetcode 题解 - 二分查找：系统讲解了二分查找中 h = m 与 h = m - 1、循环条件 l < h 与 l <= h 的边界配合，对理解逐行二分方案及其失效边界有帮助。

七、小结

• 在行列均递增的二维数组中查找目标值，从右上角（或左下角）出发的阶梯查找是标准解法：小于当前值排除本列，大于当前值排除本行，命中即返回；
• 时间复杂度 O(M + N)、空间复杂度 O(1)，严格优于暴力 O(M×N) 与逐行二分 O(M × log N)；
• 实现时必须处理 null、0 行、0 列等边界输入；
• 方法依赖"行有序 + 列有序"双重约束，缺少任一约束时应退回到逐行/逐列二分的思路。