240. 搜索二维矩阵 II

难度：🟡 Medium | 标签：矩阵、分治、Z 字搜索 | 状态：⬜ LeetCode 链接

思路

从右上角出发，比较当前元素：

• 等于 target → 找到
• 小于 target → 往下（去更大区域）
• 大于 target → 往左（去更小区域）

每步排除一行或一列，O(R+C)。

代码

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

复杂度

• 时间 O(R + C)，空间 O(1)

易错 / 回顾

• 左下角同样可行（向上 / 向右），左上 / 右下不行
• 不要朴素行二分 + 列二分，那是 O(R log C)，不如 Z 字搜索
• 注意区分 74 题（严格有序）和 240 题（每行 / 每列有序但跨行无序）