难度: Easy
给你一个 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
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 100-100 <= grid[i][j] <= 100进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？
运行时间: 19 ms
内存: 17.0 MB
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
for i in range(m):
if min(grid[i]) >= 0:
continue
for j in range(n):
if grid[i][j] < 0:
count += n - j
break
return count
这个题解使用了逐行扫描的方法来统计负数的数量。首先，它检查每一行的最小元素（即行的最后一个元素，因为行是非严格递减的），如果这个元素是非负的，那么这一行就不包含负数，可以直接跳过。如果这个元素是负数，那么它从当前行的开头开始扫描，直到找到第一个负数，然后通过'剩余列数'来增加负数的计数（因为后面的元素都是负数），然后跳出循环进入下一行。
时间复杂度: O(m*n)
空间复杂度: O(1)
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0]) # 获取矩阵的行数和列数
count = 0 # 初始化负数计数器
for i in range(m): # 遍历每一行
if min(grid[i]) >= 0: # 如果当前行的最小元素是非负的，跳过当前行
continue
for j in range(n): # 否则，遍历当前行的元素
if grid[i][j] < 0: # 找到第一个负数
count += n - j # 增加剩余的负数数量到计数器
break # 跳出循环，因为后面的元素都是负数
return count # 返回负数的总数
在题解中，由于矩阵的每一行是非严格递减的，最后一个元素是该行中的最小元素。因此，只需检查每行的最后一个元素是否为负数即可判断该行是否含有负数。如果最后一个元素是非负的，那么整行都是非负的，无需进一步检查。
是的，这种方法在所有情况下都是正确的。因为每行是非严格递减的，一旦某个元素是负数，该元素右侧的所有元素也必定是负数。因此，可以直接通过 n - j（n是列数，j是第一个负数的索引）计算出该行剩余的负数数量。
确实，使用`min(grid[i])`进行判断增加了不必要的计算。非严格递减的性质确实意味着只需要检查每行的最后一个元素就足够了。因此，可以改进算法，直接检查每行的最后一个元素，而不是使用`min`函数，以提高算法的效率。
可以使用更高效的方法，如二分查找，来找到每行中第一个负数的位置。由于每行都是非严格递减排序的，可以利用这一点在每行应用二分查找，以更快地找到转折点（从非负到负数的位置）。这样可以减少不必要的遍历，尤其是在负数出现位置较晚的情况下，大大提高效率。