LeetCode 面试题 10.09. 排序矩阵查找

2026-03-28 HGNULB 约 4 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 面试题 10.09. 排序矩阵查找

题意分析

矩阵的每一行从左到右递增，每一列从上到下递增，判断目标值是否存在。注意它不保证“上一行末尾小于下一行开头”，因此不能像 LeetCode 74 那样把整个矩阵直接映射成一个全局有序数组做一次二分。

逐元素扫描是 $O(mn)$；逐行二分是 $O(m \log n)$，只利用了行有序。题目同时给出列有序，意味着可以从一个同时具有两个方向单调性的角落出发，每次比较排除一整行或一整列。

空矩阵或空行应返回 false。重复值不影响算法，因为只需判断存在性，不需要定位第一个位置。

解法：从右上角阶梯搜索

核心思路

从右上角 (0, n-1) 开始。这个位置向左的值都不大于它，向下的值都不小于它，所以与 target 比较后总能安全排除一个方向：

当前值大于 target：当前列从这里往下只会更大，整列不可能有答案，左移一列。

当前值小于 target：当前行左侧只会更小，整行不可能有答案，下移一行。

相等：直接返回 true。

循环不变量是：若目标存在，它一定在当前候选矩形 [row, m) × [0, col] 内。每一步删除候选矩形的一整行或一整列，且不会删除可能等于目标的位置；直到命中或候选矩形为空。

解题步骤

判空后令 row = 0、col = matrix[0].length - 1，定位右上角。

当 row < m 且 col >= 0 时比较 matrix[row][col] 与目标。

大于目标就 col--，小于目标就 row++，相等立即成功。

行越过底部或列越过左侧仍未命中，返回 false。

以矩阵 [[1,4,7],[2,5,8],[3,6,9]] 查找 5 为例：右上角 7 大于 5，左移到 4；4 小于 5，下移到 5，命中。两次移动分别排除了最右列与第一行左侧，不会漏掉目标。

代码实现

// 候选区域始终是左下方矩形，每步排除一行或一列。
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            int current = matrix[row][col];
            if (current == target) {
                return true;
            }
            if (current > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
}

// 候选区域始终是左下方矩形，每步排除一行或一列。
func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    row, col := 0, len(matrix[0])-1
    for row < len(matrix) && col >= 0 {
        current := matrix[row][col]
        if current == target {
            return true
        }
        if current > target {
            col--
        } else {
            row++
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(m+n)$。行指针最多向下移动 m 次，列指针最多向左移动 n 次，二者都不回退。

空间复杂度：$O(1)$。

关键点总结

右上角和左下角都是“一边增、一边减”的信息角；左上与右下两个方向同增，比较后无法决定排除哪一半。

面试时应先区分本题与 74：本题只保证行列分别有序，不能展平二分；阶梯搜索才同时使用两维单调性。

正确性表达围绕候选矩形不变量：大就删列，小就删行，每次删掉的区域都不可能含目标。

逐行二分也能通过，但复杂度 $O(m\log n)$，在矩阵接近方阵时不如 $O(m+n)$，且浪费了列有序条件。

易错点总结

把矩阵直接展平二分：[[1,4],[2,5]] 展平为 [1,4,2,5] 并不有序，查找可能失败。

当前值大时向下、小时向左：方向完全反了，候选值只会离目标更远。大要左移，小要下移。

循环条件用 row < m || col >= 0：任一坐标越界后仍继续访问，产生数组越界；必须同时合法。

未处理空矩阵就读取第一行长度：matrix = [] 会直接越界，应在入口判空。

相似题目

题目	难度	考察点
74. 搜索二维矩阵	中等	矩阵搜索
240. 搜索二维矩阵 II	中等	矩阵搜索
剑指 Offer 04. 二维数组中的查找	中等	矩阵搜索