vvrf / DSA.log

问题拆解

矩阵每行从左到右递增、每列从上到下递增，问 target 在不在里面。暴力扫全表是 O(mn)；对每一行做二分是 O(m log n)，好一些，但它只用上了“行有序”，列方向的有序性完全浪费了。

想同时用上两个方向的有序性，就要找一个特殊的起点。右上角就是这样的位置：它是所在行的最大值，又是所在列的最小值。拿它和 target 比较，无论结果如何都能得到确定的结论——如果它比 target 大，那它下方整列都更大，这一列可以整体划掉；如果它比 target 小，那它左边整行都更小，这一行可以整体划掉。

右上角看出去，往左递减、往下递增——这正是一棵二叉搜索树的形状。每次比较砍掉一整行或一整列，搜索路径最长 m + n 步。

从右上角出发的阶梯搜索

public boolean searchMatrix(int[][] matrix, int target) {
    int i = 0, j = matrix[0].length - 1; // 从右上角出发
    while (i < matrix.length && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            j--; // 这一列都比 target 大，左移
        } else {
            i++; // 这一行都比 target 小，下移
        }
    }
    return false;
}

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    i, j = 0, len(matrix[0]) - 1  # 从右上角出发
    while i < len(matrix) and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] > target:
            j -= 1  # 这一列都比 target 大，左移
        else:
            i += 1  # 这一行都比 target 小，下移
    return False

func searchMatrix(matrix [][]int, target int) bool {
    i, j := 0, len(matrix[0])-1 // 从右上角出发
    for i < len(matrix) && j >= 0 {
        switch {
        case matrix[i][j] == target:
            return true
        case matrix[i][j] > target:
            j-- // 这一列都比 target 大，左移
        default:
            i++ // 这一行都比 target 小，下移
        }
    }
    return false
}

pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let mut i = 0usize;
    let mut j = matrix[0].len() as i32 - 1; // 列用 i32，允许减到 -1
    while i < matrix.len() && j >= 0 {
        let v = matrix[i][j as usize];
        if v == target {
            return true;
        } else if v > target {
            j -= 1; // 这一列都比 target 大，左移
        } else {
            i += 1; // 这一行都比 target 小，下移
        }
    }
    false
}

起点的选择只有右上角和左下角可行。左上角不行：它是全局最小，target 比它大时行列两个方向都可能，比较不产生任何排除。指针的移动是单向的——i 只增、j 只减，所以循环最多执行 m + n 次，不会回头也不会死循环。Rust 版把列下标声明成 i32，是为了让 j 能自然减到 -1 结束循环，避免 usize 下溢。

复杂度

指标	复杂度	原因
时间	`O(m + n)`	每次比较让 i 或 j 单向前进一步
空间	`O(1)`	只用两个下标

可以迁移的模式

在多维有序结构里找一个“比较结果能给出确定方向”的观察点，右上角、左下角这类极值角往往就是；
两个指针各自单调移动，总步数就是它们行程之和，复杂度一眼可知；
把矩阵视作隐式二叉搜索树，是“换个视角结构就显形”的典型例子。

第 74 题“搜索二维矩阵”的行间也有序，可以整体二分到 O(log mn)；本题行间无序，阶梯搜索就是最优雅的答案。