好的，我们这次来详细讲解 LeetCode 第 240 题「搜索二维矩阵 II」。

1. 题目描述

题意：
给定一个 m x n 的矩阵 matrix，矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

请编写一个高效的算法，判断目标值 target 是否存在于矩阵中。

示例：

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 → 返回 true
target = 20 → 返回 false

2. 题目特性分析

这个矩阵不是完全有序（比如按行展开后不是整体升序），但有一个很强的局部有序性：

• 从左上角到右下角并不是单调的，但我们可以利用：
  • 任意元素右面的元素 ≥ 它
  • 任意元素下面的元素 ≥ 它

这个特性意味着，如果我们从矩阵的右上角或左下角出发，可以做出确定的移动决策。

3. 暴力解法（不推荐）

最直接的方法是遍历整个矩阵，时间复杂度 O(m × n)，在矩阵很大时效率很低。
题目要求高效算法，所以我们需要利用矩阵的有序性。

4. 逐行二分查找（较好但不是最优）

因为每一行是升序的，可以在每一行进行二分查找。
时间复杂度：O(m × log n)，当 m 和 n 都很大时，比暴力好，但还可以更优。

5. 最优解法：Z 字形搜索（从右上角出发）

核心思路：
从矩阵的右上角 (row, col) = (0, n-1) 开始搜索：

• 如果 matrix[row][col] == target，找到目标，返回 true。
• 如果 matrix[row][col] > target，那么当前元素所在列下面的所有元素都会比 target 大（因为列是升序的），所以可以向左移动一列（col--）。
• 如果 matrix[row][col] < target，那么当前元素所在行左边的所有元素都会比 target 小（因为行是升序的），所以可以向下移动一行（row++）。

这样每次比较可以排除一行或一列，直到找到目标或越界。

为什么选右上角（或左下角）？
因为右上角元素是该行的最大值、该列的最小值，这样我们可以根据与 target 的比较决定是向左（变小）还是向下（变大），不会错过可能区域。
如果从左上角开始，向右和向下都是变大，无法确定方向；从右下角开始同理，向左和向上都是变小，也无法确定方向。

6. 举例说明

以示例矩阵，target = 5 为例：

1. 初始位置 (0,4)，值为 15，15 > 5 → 向左到 (0,3)，值为 11，11 > 5 → 向左到 (0,2)，值为 7，7 > 5 → 向左到 (0,1)，值为 4，4 < 5 → 向下到 (1,1)，值为 5，找到目标。

路径：15(左) → 11(左) → 7(左) → 4(下) → 5 ✅

再试 target = 20：

1. 初始 (0,4)=15，15 < 20 → 向下到 (1,4)=19，19 < 20 → 向下到 (2,4)=22，22 > 20 → 向左到 (2,3)=16，16 < 20 → 向下到 (3,3)=17，17 < 20 → 向下到 (4,3)=26，26 > 20 → 向左到 (4,2)=23，23 > 20 → 向左到 (4,1)=21，21 > 20 → 向左到 (4,0)=18，18 < 20 → 向下越界，结束，返回 false。

7. 算法步骤

1. 初始化 row = 0, col = n - 1。
2. 当 row < m 且 col >= 0 时循环：
   • 如果 matrix[row][col] == target，返回 true。
   • 如果 matrix[row][col] > target，则 col--。
   • 否则 row++。
3. 循环结束未找到，返回 false。

8. 复杂度分析

• 时间复杂度：O(m + n)
  最坏情况从右上角走到左下角，最多 m + n - 1 步。
• 空间复杂度：O(1)
  只用了几个变量。

9. 代码实现（Python）

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

10. 总结

这道题的关键是利用矩阵的局部有序性，选择一个合适的起点（右上角或左下角），使得每次比较能排除一行或一列，从而在 O(m + n) 时间内完成搜索。
这种思路在有序矩阵的搜索问题中非常经典，记住“右上角出发，大则左移，小则下移”的口诀即可。