题目

给你一个 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
进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？
来源：力扣（LeetCode）

解题思路

  题目给出了一个矩阵并且按行按列都是(非严格)单调递减的。要想统计矩阵中的负数可以直接遍历整个矩阵，但是这样的时间复杂度就会达到O(mn)，好好利用行列的递减性质也许可以达到题目的进阶条件。
  正常遍历矩阵的某一行，如果遇到的值为负数那么它后面的值也是负数，遍历矩阵的列，如果某一行的第一个值为负数那么下面所有行的值均为负数。

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m=len(grid)
        n=len(grid[0])
        s=0
        for i in range(m):
            if grid[i][0]<0:
                s+=(m-i)*n
                break
            else:
                for j in range(n):
                    if grid[i][j]<0:
                        s+=n-j
                        break
        return s