LeetCode 每日一题 - 1351. 统计有序矩阵中的负数

简单的矩阵题。

题面

给你一个 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.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

思路

鉴于题目里提到按照行与列均递减，所以可以直接从左下扫到右上，记录当前行负数位置，换行时直接从该位置启动。

代码

0ms

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int current = 0;
        int ans = 0;
        for(int i=grid.size()-1;i>=0;i--){
            for(int o=current;o<grid[i].size();o++){
                // printf("Scanning %d, grid[%d][%d] = %d\n",o,i,o,grid[i][o]);
                current = o;
                if(grid[i][o] < 0){
                    ans+=(grid[i].size() - 1) - current + 1;
                    break;
                }
            }
            // printf("Row %d end, negative now %d\n", i, ans);
        }
        return ans;
    }
};