1351. Count Negative Numbers in a Sorted Matrix

https://leetcode.com/problems/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.

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

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

++++++ ++++-- ++++-- +++--- +----- +-----

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

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;
    }
};