题目描述
思路解析动画文字版
记牢这两条:脚下非负就右移,把当前这一列从未处理区甩掉,脚下为负就把这一行从当前列到末尾整段记成负数、再上移。指针从左下角出发,一路往右上角方向走,绝不回头,所以又快又稳。下面一步一步走给你看。
起步 · 指针落在左下角 (3, 0)：先把指针放在左下角,也就是第 3 行第 0 列,这格的值是 1。负数累计先记 0。从这个角出发有个好处:往右走能甩掉确认非负的列,往上走能跳过已经数完的整行,两个方向各管一件事,互不打架。
检视 (3, 0) · 值 1：看脚下第 3 行第 0 列,值是 1,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 1 更大,所以第 0 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
右移 · 列 0 甩掉,指针到列 1：把刚站过的那格标成蓝色,它是第 0 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 1 列,行号还是 3。负数累计仍是 0,因为刚才那格不是负数。接着检视新的脚下格。
检视 (3, 1) · 值 0：看脚下第 3 行第 1 列,值是 0,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 0 更大,所以第 1 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
右移 · 列 1 甩掉,指针到列 2：把刚站过的那格标成蓝色,它是第 1 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 2 列,行号还是 3。负数累计仍是 0,因为刚才那格不是负数。接着检视新的脚下格。
检视 (3, 2) · 值 -1：看脚下第 3 行第 2 列,值是 -1,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -1 更小,所以第 3 行从第 2 列一直到行末,全都是负数。
整段计数 · 行 3 记入 3 个负数：第 3 行从第 2 列到第 4 列,一共 3 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 2 正好等于 3,一次把这一整段记进去。负数累计从 0 加到 3。
上移 · 指针到行 2：这一行的负数段记完了,指针上移到第 2 行,列号还停在 2。上面的行还没处理,它的负数段不会比这一行更长,继续在新的脚下格判断。负数累计现在是 3。
检视 (2, 2) · 值 0：看脚下第 2 行第 2 列,值是 0,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 0 更大,所以第 2 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
右移 · 列 2 甩掉,指针到列 3：把刚站过的那格标成蓝色,它是第 2 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 3 列,行号还是 2。负数累计仍是 3,因为刚才那格不是负数。接着检视新的脚下格。
检视 (2, 3) · 值 -1：看脚下第 2 行第 3 列,值是 -1,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -1 更小,所以第 2 行从第 3 列一直到行末,全都是负数。
整段计数 · 行 2 记入 2 个负数：第 2 行从第 3 列到第 4 列,一共 2 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 3 正好等于 2,一次把这一整段记进去。负数累计从 3 加到 5。
上移 · 指针到行 1：这一行的负数段记完了,指针上移到第 1 行,列号还停在 3。上面的行还没处理,它的负数段不会比这一行更长,继续在新的脚下格判断。负数累计现在是 5。
检视 (1, 3) · 值 1：看脚下第 1 行第 3 列,值是 1,它大于等于 0。这一列从上往下越来越小,上面的同列格子只会比 1 更大,所以第 3 列从这格往上一个负数都没有,它下方的行之前已经数过了,可以把这一列从未处理区甩掉。
右移 · 列 3 甩掉,指针到列 4：把刚站过的那格标成蓝色,它是第 3 列已确认非负的边界格,这一列就此从未处理区甩掉,指针右移到第 4 列,行号还是 1。负数累计仍是 5,因为刚才那格不是负数。接着检视新的脚下格。
检视 (1, 4) · 值 -2：看脚下第 1 行第 4 列,值是 -2,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -2 更小,所以第 1 行从第 4 列一直到行末,全都是负数。
整段计数 · 行 1 记入 1 个负数：第 1 行从第 4 列到第 4 列,一共 1 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 4 正好等于 1,一次把这一整段记进去。负数累计从 5 加到 6。
上移 · 指针到行 0：这一行的负数段记完了,指针上移到第 0 行,列号还停在 4。上面的行还没处理,它的负数段不会比这一行更长,继续在新的脚下格判断。负数累计现在是 6。
检视 (0, 4) · 值 -1：看脚下第 0 行第 4 列,值是 -1,它小于 0,是个负数。这一行从左往右越来越小,它右边的同行格子只会比 -1 更小,所以第 0 行从第 4 列一直到行末,全都是负数。
整段计数 · 行 0 记入 1 个负数：第 0 行从第 4 列到第 4 列,一共 1 个格子,连同脚下这格一起全部标红,它们都已计为负数,橙色指针也随之并入这段红格。用列数 5 减去当前列号 4 正好等于 1,一次把这一整段记进去。负数累计从 6 加到 7。
上移 · 指针到行 -1(已走出上边界)：指针上移后已经越过最上面的行,纵向也走到头了,循环结束。所有负数都数完,累计停在 7。
数完 · 负数共 7 个：指针一路从左下角走到右上方向出界,标红的格子就是全部负数。把侧栏几段加起来,3 加 2 加 1 加 1,正好 7 个。整个过程指针只走了行数加列数这么多步,没有逐格扫描,这就是 O(m 加 n) 的阶梯走法。
边界想清:全负时逐行整段相加、全非负含 0 时一路右移返回 0、单格时一步出界。注意 0 始终算非负、不计数。
面试重点:两个方向单调所以指针不回头、换右上角起步要把动作镜像、只行有序时退化成每行二分的 O(m 乘 log n)。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(m + n)，m 是行数,n 是列数。指针从左下角出发,每一步要么向右(列号加一)要么向上(行号减一),两个方向都只增不减,最多走 m 加 n 步就出界,所以时间是 O(m 加 n)。对比逐格扫描的 O(m 乘 n),在大矩阵上快很多
- 空间：O(1)，全程只用了 i、j、ans 三个整数变量,没有开任何额外的数组或矩阵副本。无论矩阵多大,占用的额外空间都是常数,所以空间是 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么从左下角出发能保证不回头就数全?
追问从右上角出发可以吗,动作怎么变?
追问如果矩阵只是行有序、列没有序,这套走法还成立吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
矩阵中的幸运数
LeetCode 1380 · 简单 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题