统计有序矩阵中的负数 图解题解
这道题到底在问什么
- 输入
- grid=[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
- 输出
- 8
- 输入
- grid=[[3,2],[1,0]]
- 输出
- 0
最优解：一步一步想明白
- 3记牢这两条:脚下非负就右移,把当前这一列从未处理区甩掉,脚下为负就把这一行从当前列到末尾整段记成负数、再上移。指针从左下角出发,一路往右上角方向走,绝不回头,所以又快又稳。下面一步一步走给你看。
- 4橙格 = 当前指针;红格 = 已计负数;蓝格 = 已确认非负的边界格先把指针放在左下角,也就是第 3 行第 0 列,这格的值是 1。负数累计先记 0。从这个角出发有个好处:往右走能甩掉确认非负的列,往上走能跳过已经数完的整行,两个方向各管一件事,互不打架。
- 5脚下非负,准备右移甩列看脚下第 3 行第 0 列,值是 1,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 1 更大,所以第 0 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
- 6橙格 = 新的当前指针把刚站过的那格标成蓝色,它是第 0 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 1 列,行号还是 3。负数累计仍是 0,因为刚才那格不是负数。接着检视新的脚下格。
- 7脚下非负,准备右移甩列看脚下第 3 行第 1 列,值是 0,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 0 更大,所以第 1 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
- 8橙格 = 新的当前指针把刚站过的那格标成蓝色,它是第 1 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 2 列,行号还是 3。负数累计仍是 0,因为刚才那格不是负数。接着检视新的脚下格。
- 9脚下为负,准备整段计数看脚下第 3 行第 2 列,值是 -1,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -1 更小,所以第 3 行从第 2 列一直到行末,全都是负数。
- 10红格 = 这一段全是负数(含脚下这格)第 3 行从第 2 列到第 4 列,一共 3 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 2 正好等于 3,一次把这一整段记进去。负数累计从 0 加到 3。
- 11橙格 = 新的当前指针这一行的负数段记完了,指针上移到第 2 行,列号还停在 2。上面的行还没处理,它的负数段不会比这一行更长,继续在新的脚下格判断。负数累计现在是 3。
- 12脚下非负,准备右移甩列看脚下第 2 行第 2 列,值是 0,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 0 更大,所以第 2 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
- 13橙格 = 新的当前指针把刚站过的那格标成蓝色,它是第 2 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 3 列,行号还是 2。负数累计仍是 3,因为刚才那格不是负数。接着检视新的脚下格。
- 14脚下为负,准备整段计数看脚下第 2 行第 3 列,值是 -1,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -1 更小,所以第 2 行从第 3 列一直到行末,全都是负数。
- 15红格 = 这一段全是负数(含脚下这格)第 2 行从第 3 列到第 4 列,一共 2 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 3 正好等于 2,一次把这一整段记进去。负数累计从 3 加到 5。
- 16橙格 = 新的当前指针这一行的负数段记完了,指针上移到第 1 行,列号还停在 3。上面的行还没处理,它的负数段不会比这一行更长,继续在新的脚下格判断。负数累计现在是 5。
- 17脚下非负,准备右移甩列看脚下第 1 行第 3 列,值是 1,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 1 更大,所以第 3 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
- 18橙格 = 新的当前指针把刚站过的那格标成蓝色,它是第 3 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 4 列,行号还是 1。负数累计仍是 5,因为刚才那格不是负数。接着检视新的脚下格。
- 19脚下为负,准备整段计数看脚下第 1 行第 4 列,值是 -2,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -2 更小,所以第 1 行从第 4 列一直到行末,全都是负数。
- 20红格 = 这一段全是负数(含脚下这格)第 1 行从第 4 列到第 4 列,一共 1 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 4 正好等于 1,一次把这一整段记进去。负数累计从 5 加到 6。
- 21橙格 = 新的当前指针这一行的负数段记完了,指针上移到第 0 行,列号还停在 4。上面的行还没处理,它的负数段不会比这一行更长,继续在新的脚下格判断。负数累计现在是 6。
- 22脚下为负,准备整段计数看脚下第 0 行第 4 列,值是 -1,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -1 更小,所以第 0 行从第 4 列一直到行末,全都是负数。
- 23红格 = 这一段全是负数(含脚下这格)第 0 行从第 4 列到第 4 列,一共 1 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 4 正好等于 1,一次把这一整段记进去。负数累计从 6 加到 7。
- 24已走出上边界,数完指针上移后已经越过最上面的行,纵向也走到头了,循环结束。所有负数都数完,累计停在 7。
- 25红格 = 全部 7 个负数指针一路从左下角走到右上方向出界,标红的格子就是全部负数。把侧栏几段加起来,3 加 2 加 1 加 1,正好 7 个。整个过程指针只走了行数加列数这么多步,没有逐格扫描,这就是 O(m 加 n) 的阶梯走法。
⚠️ 容易写错的地方
✗ 错：把 0 也当成负数计进去
✓ 对：只有严格小于 0 的才算负数,等于 0 不算,判断要用脚下值小于 0
题目数到的是负数,0 是非负数。把脚下值大于等于 0 归到右移那一支,正好把 0 排除在外
✗ 错：为负时只记当前一格,忘了整行后缀
✓ 对：脚下为负时,这一行从当前列到行末全是负数,要一次加 n 减 j 个
行从左到右非递增,当前格已是负数,右边只会更小、必然也都是负数,逐格再判会退化成 O(m 乘 n)
✗ 错：计完一段忘了上移、或右移时多记了数
✓ 对：为负是整段计数后上移 i 减一;非负是右移 j 加一且不计数
两个分支动作不能串味:右移那格本身非负不该计;上移是因为本行后缀已数完,跳到更短的上一行
✗ 错：起点放错角导致两个方向打架
✓ 对：从左下角起步,右移甩列、上移跳行;若从右上角起步,则脚下为负按 m 减 i 整段记入再左移、非负才下移,逻辑要整体镜像对应
只有选在让一个方向单调判正、另一个方向单调计数的角,指针才能不回头一次走完
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
i, j = m - 1, 0
ans = 0
while i >= 0 and j < n:
if grid[i][j] >= 0:
j += 1
else:
ans += n - j
i -= 1
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int i = m - 1;
int j = 0;
int ans = 0;
while (i >= 0 && j < n) {
if (grid[i][j] >= 0) {
j++;
} else {
ans += n - j;
i--;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countNegatives(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int i = m - 1;
int j = 0;
int ans = 0;
while (i >= 0 && j < n) {
if (grid[i][j] >= 0) {
j++;
} else {
ans += n - j;
i--;
}
}
return ans;
}
}复杂度
时间
O(m + n)
m 是行数,n 是列数。指针从左下角出发,每一步要么向右(列号加一)要么向上(行号减一),两个方向都只增不减,最多走 m 加 n 步就出界,所以时间是 O(m 加 n)。对比逐格扫描的 O(m 乘 n),在大矩阵上快很多
空间
O(1)
全程只用了 i、j、ans 三个整数变量,没有开任何额外的数组或矩阵副本。无论矩阵多大,占用的额外空间都是常数,所以空间是 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计有序矩阵中的负数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么从左下角出发能保证不回头就数全?+
关键在两个方向各自单调。左下角往上,同一列越往上越大;往右,同一行越往右越小。脚下非负时,这一列从这格往上都非负,可以安心右移、把这一列从未处理区甩掉,绝不会漏掉这列还没数的负数,因为这格往上根本没有,它下方的行早已数过。脚下为负时,这一行从这格往右都为负,一次记入整段后,本行剩下的负数都处理完了,可以上移到更短的上一行。每一步都把一整列或一整行的负数情况彻底定下来,所以指针只进不退,一次走完。
从右上角出发可以吗,动作怎么变?+
可以,本质一样,只是把两个方向镜像过来。右上角往下同列越来越小、往左同行越来越大。这时脚下为负就向左移,因为这一列从这往下都更小、都是负数可以按列整段记;脚下非负就向下移去找负数。无论从哪个角起步,核心都是选一个让一个方向单调用来判断、另一个方向单调用来整段计数的角,指针才能不回头。参考代码选的是左下角。
如果矩阵只是行有序、列没有序,这套走法还成立吗?+
不成立。阶梯走法甩掉整列的前提,是列也非递增,这样脚下非负才能断定上面同列也非负。如果列没有序,脚下非负推不出整列非负,就不能甩列。那种情况只能退一步:对每一行单独二分,找出这行第一个负数的位置,用列数减去它得到这行的负数个数,m 行各二分一次,总时间是 O(m 乘 log n)。比逐格扫快,但不如行列双有序时的 O(m 加 n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计有序矩阵中的负数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。