1351.统计有序矩阵中的负数：O(m+n)时间复杂度——抽象题解

【LetMeFly】1351.统计有序矩阵中的负数：O(m+n)时间复杂度——抽象题解

力扣题目链接：https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/

给你一个 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

 

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

解题方法：遍历

例如样例数组：

 4  3  2 -1
 3  2  1 -1
 1  1 -1 -2
-1 -1 -2 -3

不难发现其实是这样的：

 4  3  2  |  -1
 3  2  1 /  -1
 1  1   / -1 -2
-------+
-1 -1 -2 -3

看到中间那条分隔线了吗？我们按照中间那条线遍历就好了。

使用一个纵坐标变量，默认值为最后一列。接着从第一行开始往下遍历：

对于当前行，让纵坐标移动到第一个非负数的位置（或移出数组）。具体而言：

对于当前行，在纵坐标没有越界且当前所指元素为负数时，纵坐标不断左移。

• 时间复杂度$O(m+n)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2025-12-28 14:45:14
 */
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        for (int i = 0, j = m - 1; i < n; i++) {
            while (j >= 0 && grid[i][j] < 0) {
                j--;
            }
            ans += m - j - 1;
        }
        return ans;
    }
};

/*
[[4,3,2,-1],
 [3,2,1,-1],
 [1,1,-1,-2],
 [-1,-1,-2,-3]]
*/

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源