搜索二维矩阵 II 图解题解

这道题到底在问什么

matrix

[[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]]

target

5

输出

true（5 在第 2 行第 2 列）

先想最直接的笨办法

cur 现在指着 5，正好等于 target。直接返回 true。全程只比了 4 次，而暴力要扫 16 格。（动画第 9 步）

最优解：一步一步想明白

1. 3最笨的办法是一格一格全看一遍，4×4 要看 16 格，m×n 就是 O(m乘n)。可矩阵明明是排好序的，全扫等于白白浪费了顺序信息。
2. 4看右上角那个数：它是所在行里最大的，又是所在列里最小的。这种"一头大一头小"的位置，每比一次都能砍掉一整行或一整列。
3. 5cur 站在右上角 (0,3)=11，要找 target=5起点放在右上角：第 0 行第 3 列，值是 11。下面看 11 和 5 谁大。
4. 611 大于 5 → 这一整列都比 5 大 → c 减 1，左移到 711 大于 5。因为列是升序的，11 下面的 12、16、17 只会更大，整列都不可能是 5。所以把第 3 列划掉，cur 左移一格到 7。
5. 77 大于 5 → 再删一列 → c 减 1，左移到 47 还是大于 5，同样的道理，第 2 列也整列划掉，cur 再左移到 4。注意 cur 一直贴在第 0 行往左挪。
6. 84 小于 5 → 这一整行都比 5 小 → r 加 1，下移到 54 小于 5。4 左边的 1 更小，所以第 0 行剩下的都比 5 小，整行划掉。这次方向变了：cur 向下走一格，落在 5。
7. 9matrix[1][1] = 5 = target → 找到了，return truecur 现在指着 5，正好等于 target。直接返回 true。全程只比了 4 次，而暴力要扫 16 格。
8. 10左、左、下、命中：只往左或往下，从不回头把高亮的几格连起来看：11、7、4、5。cur 要么向左、要么向下，永远不回头。这正是 O(m+n) 的来历——每走一步就少一行或一列。
9. 13这就是本题的灵魂：选一个比较结果能二选一排除的起点，让每次比较都把搜索范围缩小一整行或一整列。
10. 15(0,0)=1 ＜ 5：往右是 4、往下是 2，两边都更大，没法排除谁如果从左上角 1 开始：1 小于 5，但右边 4 和下面 2 都比 1 大，根本不知道 5 在右边还是下边，没法砍掉任何一边——这就是必须从右上或左下起步的原因。
11. 19这套思路的内核是：在有序结构里选一个比较结果能确定唯一排除方向的位置。练熟后可去专题里找同类矩阵 / 双指针题继续迁移，卡住就问小欧或开通关训练。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def searchMatrix(self, matrix, target):
        r, c = 0, len(matrix[0]) - 1   # 起点：右上角
        while r < len(matrix) and c >= 0:
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                c -= 1                  # 太大，左移砍一列
            else:
                r += 1                  # 太小，下移砍一行
        return False

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int r = 0, c = (int)matrix[0].size() - 1;   // 右上角
        while (r < (int)matrix.size() && c >= 0) {
            if (matrix[r][c] == target) return true;
            else if (matrix[r][c] > target) c--;        // 左移
            else r++;                                     // 下移
        }
        return false;
    }
};

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int r = 0, c = matrix[0].length - 1;   // 右上角
        while (r < matrix.length && c >= 0) {
            if (matrix[r][c] == target) return true;
            else if (matrix[r][c] > target) c--;   // 左移
            else r++;                              // 下移
        }
        return false;
    }
}

# 适用：行列均单调的矩阵里查值
r, c = 0, len(matrix[0]) - 1     # ← 起点必须是能二选一排除的角
while r < ____ and c >= ____:     # ← 守住两条边界
    v = matrix[r][c]
    if v == target: return True
    elif v > target: c -= 1       # ← 太大，砍掉当前列
    else:            r += 1       # ← 太小，砍掉当前行
return False

// 行列均单调的矩阵里查值
int r = 0, c = (int)matrix[0].size() - 1;   // 右上角起点
while (r < /*行数*/ && c >= /*0*/) {
    int v = matrix[r][c];
    if (v == target) return true;
    else if (v > target) c--;   // 太大→左
    else r++;                   // 太小→下
}
return false;

// 行列均单调的矩阵里查值
int r = 0, c = matrix[0].length - 1;   // 右上角起点
while (r < /*行数*/ && c >= /*0*/) {
    int v = matrix[r][c];
    if (v == target) return true;
    else if (v > target) c--;   // 太大→左
    else r++;                   // 太小→下
}
return false;

复杂度

面试官可能追问