【算法详解】力扣240.搜索二维矩阵II

一、 题目描述

力扣链接：力扣240.搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

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

二、思路分析

题目提到该矩阵是从左到右，从上到下递增的，那么我们就要利用这个性质，从矩阵的某一个角落出发，每一次往一个方向移动，直到找到目标值。

对于这道题，可以从右上角或左下角出发，因为这两个角落的两个方向是不同的单调方向，如果从左上角或右下角出发，那么我们就没办法判断下一步到底往哪个方向移动。

以右上角出发，如果当前值小于目标值，那么就往下走，反之就往左走。

三、C++题解

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 从右上角开始遍历，每次只能往左或往下
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;

        while (i < m && j >= 0) {
            if (matrix[i][j] > target) {
                --j;
            }
            else if (matrix[i][j] < target){
                ++i;
            }
            else {
                return true;
            }
        }

        return false;
    }
};