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)$，只使用了常数个指针变量进行索引查找。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

import sys

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

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.searchMatrix(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py