好的，我们这次来详细讲解 LeetCode 第 240 题：搜索二维矩阵 II（Search a 2D Matrix II）。

1. 题目描述

题意：
编写一个高效的算法来搜索 m x n 矩阵中的一个目标值 target。该矩阵具有以下特性：

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

示例：

矩阵：
[
  [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

注意：

• 不能把它当成每行首元素大于上一行首元素的“完全有序矩阵”（那是 LeetCode 74 题）。
• 本题的排序规则是：行递增、列递增，但下一行不一定大于上一行的最后一个元素。

2. 思路分析步骤

2.1 暴力法（不可取）

遍历整个矩阵，时间复杂度 O(m × n)，没有利用有序特性，不是高效解法。

2.2 逐行二分查找

• 对每一行进行二分查找，因为行内有序。
• 时间复杂度：O(m log n)，如果 m 和 n 相近，就是 O(n log n)。
• 比暴力法好，但还能更优吗？可以做到 O(m + n)。

2.3 利用矩阵排序特性寻找起点

观察矩阵：

• 左上角最小，右下角最大，但这两个点作为起点不方便缩小范围。
• 如果从右上角开始：
  • 向左走会变小
  • 向下走会变大
• 如果从左下角开始：
  • 向上走会变小
  • 向右走会变大

这样我们可以一次排除一行或一列。

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

步骤：

1. 初始位置 (row, col) = (0, n-1)，即矩阵右上角。
2. 比较 matrix[row][col] 与 target：
   • 如果相等 → 找到目标，返回 true。
   • 如果 matrix[row][col] > target，说明当前元素太大，这一列下面的所有元素都会更大，所以这一列不可能有目标，col--（左移一列）。
   • 如果 matrix[row][col] < target，说明当前元素太小，这一行左边的所有元素都会更小，所以这一行不可能有目标，row++（下移一行）。
3. 如果 row 或 col 越界，说明没找到，返回 false。

为什么正确？

• 因为矩阵的排序规则保证了：
  • 向左是递减
  • 向下是递增
• 所以每次比较都能排除一行或一列，而不会错过目标。

4. 举例说明

矩阵：

[
  [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。

1. 起点 (0,4)=15，15 > 5 → 左移 col=3 → (0,3)=11
2. 11 > 5 → 左移 col=2 → (0,2)=7
3. 7 > 5 → 左移 col=1 → (0,1)=4
4. 4 < 5 → 下移 row=1 → (1,1)=5 → 找到，返回 true。

找 target = 20：

1. (0,4)=15 < 20 → 下移 row=1 → (1,4)=19 < 20 → 下移 row=2 → (2,4)=22
2. 22 > 20 → 左移 col=3 → (2,3)=16 < 20 → 下移 row=3 → (3,3)=17 < 20 → 下移 row=4 → (4,3)=26
3. 26 > 20 → 左移 col=2 → (4,2)=23 > 20 → 左移 col=1 → (4,1)=21 > 20 → 左移 col=0 → (4,0)=18 < 20 → 下移 row=5 越界 → 返回 false。

5. 代码实现（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

复杂度分析：

• 时间复杂度：O(m + n)，因为每次移动会减少一行或一列。
• 空间复杂度：O(1)。

6. 总结

• 本题利用了矩阵局部有序的特性，选择右上角或左下角作为起点，可以逐步缩小搜索范围。
• 关键思路：一次比较能排除一行或一列，从而在 O(m+n) 时间内完成搜索。
• 这种“Z 字形搜索”是面试中常见的高效解法。

需要我进一步解释某个步骤，或者再举一个例子吗？