题目

给定一个 m x n 的矩阵 matrix，请编写一个高效的算法来判断目标值 target 是否存在于矩阵中。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

---

示例 1

输入：
matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
target = 5

输出：
true

解释：
目标值 5 存在于矩阵中。

---

示例 2

输入：
matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
target = 20

输出：
false

解释：
目标值 20 不存在于矩阵中。

---

提示

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列。
• 每列的所有元素从上到下升序排列。
• -10^9 <= target <= 10^9

实现

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int x = matrix.size() - 1 , y = 0;
        while(y < matrix[0].size() && x >= 0) {
            if(matrix[x][y] == target) return true;

            if(matrix[x][y] > target) x --;
            else y ++;
        }
        return false;
    }
};