# 1351. 统计有序矩阵中的负数

> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
>
> 同步博客：https://www.algomooc.com

题目来源于 LeetCode 上 1531 题。

## 题目

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 

请你统计并返回 grid 中 负数 的数目。


示例 1：


```
输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

```

示例 2：

```
输入：grid = [[3,2],[1,0]]
输出：0
```

示例 3：

```
输入：grid = [[1,-1],[-1,-1]]
输出：3
```

示例 4：


```
输入：grid = [[-1]]
输出：1

```


提示：


m == grid.length

n == grid[i].length

1 <= m, n <= 100

-100 <= grid[i][j] <= 100


## 题目解析

首先审题，在一个矩阵中找出所有负数，这个很好理解，小白一开始做，可以直接暴力遍历，然后依次判断当前值是不是小于0，小于0计数加一。如果是面试的话，面试官一般都会问还没有其他办法，这时候你肯定要说怎么没有，所以我们做一道题不能仅仅限于做出了，要从多方面下手，使得复杂度越小越好。

所以我们要仔细审题，我们看到题目中有这样一句描述**矩阵中的元素无论是按行还是按列，都以非递增顺序排列**，这句话信息量很大，你品，你仔细品。

首先我们可以理解到的是：一个 m * n 的矩阵 grid，grid[i][j]<0的话，i那一行第j个到数组最后一个都是小于0，第i行开始，j到后面的列都是小于0

我们举个例子

```
[
	[4,   3,  -1,  -1],
	[3,   2,  -1,  -1],
	[1,   1,  -1,  -2],
	[-1, -1,  -2,  -3]
]

```

可以看到第一行第三列的值小于0，那么第一行及后面几行的第三列和后面的列的值都小于0。

所以我们可以进行倒序遍历，找到负数的左边界，也就是左边第一个为负数的值。

i为行遍历的指针，j为列遍历指针，count为负数的个数，len1为**当前行**的个数，len2为**当前列**的个数

```
初始值
let count = 0；
let len1 = grid.length
let len2 = grid[0].length
let i = 0；
let j = len2 - 1；
```

然后我们倒序遍历列，行还是正序遍历，以上面的例子来说，我们找到的第一个负数是grid[0][2]，然后我们能确定的负数就有如下，所以我们count就可以加上(len1 - i -1) * (len2 - j )

```
[
	[ -1,  -1],
	[ -1,  -1],
	[ -1,  -2],
	[ -2,  -3]
]

```

然后我们遍历的矩阵就变成如下，然后重复上面操作。


```
[
	[3,   2],
	[1,   1],
	[-1, -1]
]

```

所以我们每次遍历后要更新len1和len2，具体看代码和动画。


## 动画理解


<video id="video" controls="" preload="none" >
      <source id="mp4" src="../Animation/1351.mp4"  type="video/mp4">
  </video>

## 参考代码

```JavaScript
/**
 * @param {number[][]} arr
 * @return {number}
 */
var countNegatives = function(arr) {
    if (arr.length <= 0 ) {return 0}
    let count = 0;
    let len1 = arr.length;
    let len2 = arr[0].length;
    let i = 0;
    let j = len2 - 1;
    while(i < len1) {
        while(j >= 0) {
            if (arr[i][j] < 0) {
                if (j==0){
                    count += (len2 * (len1 - i))
                    len2 = 0
                    break
                }
                 j--
            }else {
               if (len2 == j + 1) {
                    break
                }
                count += ((len2 - j - 1) * (len1 - i))
                len2 = j + 1
                break
            }
        }
        i++
        j= len2 - 1
    }
    return count
};
```

## 复杂度分析

时间复杂度： O(mn)。 因为如果矩阵中所有的数都为正数，那么要遍历整个矩阵，所以时间复杂度是O(mn)。
	

空间复杂度：O(1)。


![](../../Pictures/qrcode.jpg)