240. 搜索二维矩阵 II

题目链接：240. 搜索二维矩阵 II

题目描述

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

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

核心思考：阶梯查找法 (Staircase Search)

虽然每一行和每一列都是有序的，但整个矩阵并不像一维数组那样是严格单调的。为了利用现有的局部升序特性，我们可以从矩阵的特定角落（右上角或左下角）开始搜索。这被称为“阶梯查找法”。

以从右上角 (0, n-1) 开始搜索为例：

1. 决策点：
   • 如果当前元素 matrix[i][j] 恰好等于 target：找到目标，返回 True。
   • 如果当前元素 matrix[i][j] 小于 target：由于当前元素已经是其所在行的最大值，而 target 还要更大，因此 target 必定不在当前行。我们需要“下移”一行：i += 1。
   • 如果当前元素 matrix[i][j] 大于 target：由于当前元素已经是其所在列的最小值，而 target 还要更小，因此 target 必定不在当前列。我们需要“左移”一列：j -= 1。
2. 退出条件：
   • 只要坐标 i 或 j 越出了边界且仍未找到，说明 target 不在矩阵中，返回 False。

这种方法巧妙地利用了右上角元素作为“二叉搜索树根节点”的特性（左侧变小，下方变大），将搜索范围在每一步都缩小一行或一列。

解题思路 (Python)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        
        # 从矩阵的右上角开始搜索
        i, j = 0, n - 1
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] < target:
                # 目标值更大，由于当前行右侧已无更大值，必须向下移动
                i += 1
            else:
                # 目标值更小，由于当前列下方已无更小值，必须向左移动
                j -= 1
        return False

复杂度分析

• 时间复杂度：$O(M + N)$，其中 $M$ 为行数，$N$ 为列数。在最坏情况下，我们会从右上角走到左下角，总共步数不超过 $M+N$。
• 空间复杂度：$O(1)$，只使用了常数个指针变量进行索引查找。