O(n),其他解法未免也太啰嗦了。

    j=M-1;
    for (int i=0;i<n;++i) { 
        while (j>0 && val[i][j]>K) --j;
        if (val[i][j]==K) {cout<<"Yes"<<endl;return 0;}
    }
    cout<<"No"<<endl;return 0;

关键点在于不等关系是有传递关系的。 如果一个位置(i,j)的数>K，显然它下边、右边、右下的数一定>K，因此在后边的查询中看都不用看。 当我们按照上往下(i增加)的顺序遍历行时,发现最右侧的列不合法就直接排除就好。

没想到还得补充下时间复杂度…… 第二行for显然是O(n) 第4行while只减不增，for循环全部执行完最多减M次。也是O(n) 故总计O(n)