leetcode 1351

1351: 统计有序矩阵中的负数

利用 grid 行列有序的性质，把时间复杂度从 O(mn) 的暴力查找优化成 O(m+n)。

class Solution { public: int countNegatives(vector<vector<int>>& grid) { int m=grid.size(),n=grid[0].size(); int ans=0; int i=0,j=n-1; //从右上角开始 while(i<m && j>=0){ if(grid[i][j]<0){ ans+=m-i; //这一列剩余元素都是负数 j--; } else i++; //这一行剩余元素全都非负，排除 } return ans; } };