---
description: https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
---

# 1351. Count Negative Numbers in a Sorted Matrix

Given a `m * n` matrix `grid` which is sorted in non-increasing order both row-wise and column-wise.&#x20;

Return the number of **negative** numbers in `grid`.

**Example 1:**

```
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
```

**Example 2:**

```
Input: grid = [[3,2],[1,0]]
Output: 0
```

**Example 3:**

```
Input: grid = [[1,-1],[-1,-1]]
Output: 3
```

**Example 4:**

```
Input: grid = [[-1]]
Output: 1
```

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 100`
* `-100 <= grid[i][j] <= 100`

矩阵行和列已经都按照不递增的顺序排好，问矩阵中负数的个数。直观解法遍历每一行然后做个二分，不过由于它行和列都满足不递增，因此形成了类似这样的矩阵：

++++++\
++++--\
++++--\
+++---\
+-----\
+-----

所以可以从右上角开始向左遍历，如果遇到非负意味着前面都不可能是负数，调到下一行，同时继续保持当前遍历到的列依次接着遍历。

```cpp
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        const int M = grid.size(), N = grid[0].size();
        int c = N - 1, r = 0, res = 0;
        while (r < M) {
            if (c >= 0 && grid[r][c] < 0) --c;
            else {
                res += N - c - 1;
                ++r;
                c = N - 1;
            }
        }
        return res;
    }
};
```
