問題描述

M×N 矩陣，每行遞增，每行首元素 > 上一行尾元素。查找 target 是否存在。要求高效算法。

楊氏矩陣特性

• 行遞增、列遞增（因行首 > 上行尾）。
• 從右上角 (0, N-1) 開始：

1. 若 matrix[r][c] < target → 當前列所有元素均 < target，行下移 r++。
2. 若 matrix[r][c] > target → 當前行所有元素均 > target，列左移 c--。
3. 若相等 → 找到。

每步排除一行或一列，時間 O(M+N)。

代碼實現

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

替代方案：二分查找 O(log(MN))

將二維矩陣視為一維數組：idx = r*n + c，r = idx/n, c = idx%n。標準二分查找。

bool searchMatrix(vector>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int l = 0, r = m*n - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int val = matrix[mid/n][mid%n];
        if (val < target) l = mid + 1;
        else if (val > target) r = mid - 1;
        else return true;
    }
    return false;
}

複雜度對比

• 右上角搜索：O(M+N)，代碼極簡，無溢出風險，適合面試現場寫。
• 二分查找：O(log(MN))，理論更優，但需處理一維索引映射，面試易出錯。

總結

LeetCode 74 是楊氏矩陣查找的經典入門題。右上角（或左下角）搜索利用矩陣「行增列增」特性，每步排除一行/列，邏輯清晰、代碼最短、邊界最少。掌握此模板，所有「有序矩陣查找/計數/第K小」問題均可快速切入。