A.每日一题——1351. 统计有序矩阵中的负数

题目链接：1351. 统计有序矩阵中的负数（简单）

算法原理：

解法：数学单调性

0ms击败100.00%

时间复杂度O(M+N)

咱假设m为列数，n是行数（反过来看也行，都是一样的），设置i和j分别表示列数和行数，一个放开头一个放末尾，以便利用单调性，那咱就让i放在末尾，i=m-1，j=0，然后只要还有剩余元素就一直持续找负数：

①如果发现(i,j)的元素是负数，那么该列的剩余元素也一定都是负数，ret+=n-j，然后这一列就不要了，直接去前一列继续找

②如果发现(i,j)的元素是正数，说明该行的该列不是负数，需要去下一行的此列寻找，j++

注意：这个过程是通过遍历每行来累加每列剩下全是负数的情况，充分利用了递减的单调性，所以不用再返回去重新遍历，时间复杂度从O(mn)降到了O(m+n)

Java代码：

class Solution { public int countNegatives(int[][] grid) { //这里把m看成列数，把n看成行数 int m=grid.length,n=grid[0].length; if(grid[0][0]<0) return m*n; int ret=0; int i=m-1,j=0; while(i>=0&&j<n){//还有剩余元素 if(grid[i][j]<0){ ret+=n-j;//这一列剩余元素都是负数 i--;//取该行的前一列继续找负数 }else j++;//该行的此列没有负数，去下一行的此列找，因为是递减，所以没必要再返回去重新找 } return ret; } }