Monotonicity

题目描述[原题链接][https://www.acwing.com/problem/content/description/16/]

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

算法描述

分析可知，二维数组的数字有特征的，右上角向下、向右都是递减的，所以可以从右上角开始遍历，如果array[i][j]>target向左移即j--,如果array[i][j]<target向下移，即i++，最主要的是要判断边界条件，注意出口，最后通过i,j的值返回结果即可；

C++代码

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

Java代码

class Solution {
    public boolean searchArray(int[][] array, int target) {
        if(array.length == 0||array[0].length==0)return false;
        int  i = 0;
        int j = array[0].length-1;
        
        while(j>=0&&i<array.length&&array[i][j]!=target){
            if(array[i][j]>target){
                j--;
            }else {
                i++;
            }
        }
        if(j==-1||i>array.length-1)return false;
        return true;
    }
}